Description
让我们定义A 为1， 2， 3，。。。， 2 * N - 1 的一个全排列。
定义数列B 为A 的前缀的中位数形成的数列：B[i] 为A[1]，A[2]，。。。，A[2 * i - 1] 的中位数。
注：对于M 个数的中位数（M 是奇数），可以通过排序后取中间的数得到。
给出N 和数列B。找到一个全排列A 使得前缀中位数形成的数列恰好为B。
Input
输入包含两行。
第一行包含一个整数N。
第二行描述B：N 个整数，用空格隔开。
Output
输出A：含2 * N - 1 个空格隔开的整数的一行。如果有多个全排列A 能够形成输入的数列B，
那么你可以输出任意一个。测试数据中保证总是存在解。
Sample Input
5
1 3 3 4 5
Sample Output
1 9 3 2 4 8 7 5 6
Data Constraint
? 1 <= A[i] <= 2 * N - 1，对于任意i 从1 到2 * N - 1
? 1 <= B[i] <= 2 * N - 1，对于任意i 从1 到N
? 1 <= N <= 100 000
? 60% 的数据有N <= 1000
算法讨论
从左往右贪心，a序列共有三种情况，记录l，r分别为1~2*n-1中最小和最大的没放入b序列的值
(1)a[i]=a[i-1]那么输出l,r，更新l和r
(2)a[i]>a[i-1]如果a[i]已放入，输出两次r,否则输出a[i]和r
(3)a[i]<a[i-1]如果a[i]已放入，输出两次l,否则输出a[i]和l
varf:array[0..200000] of boolean;a:array[0..200000] of longint;n,i,l,r,p:longint;
procedure jj;
beginwrite(l,' ');f[l]:=true;while (f[l])and(l<2*n-1) doinc(l);if l>r thenbegin p:=r;r:=l;l:=p;end;
end;
procedure jjj;
beginwrite(r,' ');f[r]:=true;while (f[r])and(r>0) dodec(r);if r<l thenbegin p:=r;r:=l;l:=p;end;
end;
beginassign(input,'medians.in');reset(input);//assign(output,'medians.out');rewrite(output);readln(n);for i:=1 to n doread(a[i]);f[a[1]]:=true;write(a[1],' ');l:=1;while f[l] do inc(l);r:=2*n-1;while f[n] do dec(r);for i:=2 to n dobeginif a[i]=a[i-1] thenbeginjj;jjj;end;if a[i]>a[i-1] thenif f[a[i]] thenbeginjjj;jjj;endelsebeginwrite(a[i],' ');f[a[i]]:=true;if f[l] thenwhile f[l] do inc(l);if f[r] thenwhile f[r] do dec(r);if l>r thenbegin p:=l;l:=r;r:=l;end;jjj;end;if a[i]<a[i-1] thenif f[a[i]] thenbeginjj;jj;endelsebeginwrite(a[i],' ');f[a[i]]:=true;if f[l] thenwhile f[l] do inc(l);if f[r] thenwhile f[r] do dec(r);if l>r thenbegin p:=l;l:=r;r:=l;end;jj;end;end;close(input);close(output);
end.