题目描述

设 $A$ 为 $1,2,3,\ldots,2\times N-1$ 的任意一种排列。

我们定义 $A$ 的前缀中位数为一个长度为 $N$ 的数列 $B$，$B_i$ 为 $A_1,A_2,\ldots,A_{2\times i-1}$ 的中位数。

我们将会给出 $B$ 数列，请构造一个数列 $A$，使得其前缀中位数为 $B$。

输入格式

第一行为一个整数 $N$。

接下来一行 $N$ 个整数，表示数列 $B$。

输出格式

仅一行 $2\times N+1$ 个整数，表示您构造的数列 $A$。

数据一定有解，您只需要输出其中一种。

5
1 3 3 4 5

1 9 3 2 4 8 7 5 6

提示

数据范围及限制

• 对于 $60\%$ 的数据，保证 $N\le 10^3$。
• 对于 $100\%$ 的数据，保证 $1\le N\le 10^5$，$1\le A_i,B_i\le 2\times N-1$，数据一定有解。

说明

本题译自 Balkan Olympiad in Informatics 2011 Day 1 T3 medians。

感谢