题目描述

一年一度的综艺节目《中国新毒瘤》又开始了。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

输出的 $0$ 表示选手共询问了 $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\%$，百分比乘以该测试点所在子任务满分分数即为该测试点得分；
• 一个子任务的实际得分为该子任务内所有测试点得分的最小值。

具体的评分参数如下：

$i$	$\omega_i$	$i$	$\omega_i$	$i$	$\omega_i$	$i$	$\omega_i$	$i$	$\omega_i$
$1$	$3000000$	$6$	$2000000$	$11$	$1790000$	$16$	$1710000$	$21$	$1670000$
$2$	$3000000$	$7$	$1900000$	$12$	$1770000$	$17$	$1700000$	$22$	$1665000$
$3$	$2000000$	$8$	$1850000$	$13$	$1750000$	$18$	$1690000$	$23$	$1660000$
$4$	$2000000$	$9$	$1830000$	$14$	$1730000$	$19$	$1680000$	$24$	$1655000$
$5$	$2000000$	$10$	$1800000$	$15$	$1720000$	$20$	$1675000$	$25$	$1650000$

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

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

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