题目描述

一年一度的综艺节目《中国新毒瘤》又开始了。zrsrm 从小就梦想成为一名工程师。本季度的的导师将会带领大家学会毒瘤。

轻车熟路的 zrsrm 顺利地通过了海选，接下来的环节是导师 34221-xhy 的面试，面试题是这样的：

• 在大前年的赛场上，有 $2n$ 名选手，他们将在一轮的筛选环节中进行 $n$ 场比赛，每场比赛有两个人参加，而每个人恰好参加了一场比赛。
• 现在，这 $2n$ 名选手站成了一排，你的任务则是找出每位选手的对手。为了方便，我们将选手从 $0$ 到 $2n-1$ 编号。

当然，早已忘记大前年的比赛内容的 zrsrm 答不出这道题，于是导师 34221-xhy 允许 zrsrm 询问他若干个问题，每个问题必须是这个格式：

• 第 $l$ 个选手到第 $r$ 个选手中，可以找到多少对选手参加了同一场比赛。

当然，导师 34221-xhy 对 zrsrm 的评价和他询问的次数有关，询问次数越少评价越高，你可以帮帮他吗？

任务

你需要编写一个函数，以完成题目的任务：

• match(n):
  • $n$ 表示共有 $n$ 场比赛；
  • 你需要返回一个大小为 $2n$ 的 std::vector，其中第 $i + 1$ 个元素表示编号为 $i$ 的人的对手编号。

你可以调用函数 query 以帮助你确定每个数的值。

• query(l, r):
  • $l, r$ 分别表示你询问的区间的左右端点；
  • 如果询问次数已经超过 3000000，成绩立刻将记为零分；
  • 如果 $[l, r] \not \subseteq [0, 2n)$ 或者 $l > r$，将会报错（成绩记为零分），否则会返回询问的结果。

实现细节

本题只支持 C++ 以及以上版本。

你只能提交一个源文件实现如上所述的 match 函数，并且遵循下面的命名和接口。你需要包含头文件 match.h。

std::vector<int> match(int n);

int query(int l, int r);

如果有不清楚的地方，见样例及测评库下载，内附了样例程序。

输入格式

评测系统将读入如下格式的输入数据：

第一行一个正整数 $n$。

接下来一行共 $2n$ 个整数，表示每个人的对手的编号，其中第 $i + 1$ 个数表示第 $i$ 个人的对手编号。

输出格式

评测系统将输出一个整数，表示询问的次数

5
1 0 3 2 5 4 7 6 9 8

0

数据范围与提示

共两个子任务，满分分数分别为 $40$ 分、$60$ 分。

对于每一个测试点，评测机会使用 $25$ 个评分参数 $\omega_1,\omega_2,\ldots,\omega_{25}$ 计算你的成绩，保证 $\omega_i\geq\omega_{i+1}$。

计算方法如下：

• 若你的询问次数为 $T$，则你在该测试点的得分百分比 $p = \max\{x~|~T\leq \omega_x\}\times 4\%$，百分比乘以该测试点所在子任务满分分数即为该测试点得分；
• 一个子任务的实际得分为该子任务内所有测试点得分的最小值。

具体的评分参数如下：

对于第一个子任务：$n = 1000$。

对于第二个子任务：$n = 100000$。

保证交互库的用时不会超过 $1\texttt{s}$，使用的内存空间不会超过 $256\texttt{MB}$。