접두사 중앙값

$A$를 $1, 2, 3, \ldots, 2N-1$의 순열이라고 하자.

$A$의 접두사 중앙값은 $N$개의 원소를 가진 배열 $B$로 정의하며, $B_i$는 앞의 $2i-1$개 원소 $A_1, A_2, \ldots, A_{2i-1}$의 중앙값이다.

원소가 $M$개인 목록(단, $M$은 홀수)의 중앙값은 목록을 정렬했을 때 한가운데에 오는 값이다.

$N$과 배열 $B$가 주어질 때, 접두사 중앙값이 정확히 $B$가 되는 순열 $A$를 복원하여라.

첫째 줄에 정수 $N$이 주어진다.

둘째 줄에 $N$개의 정수 $B_1, B_2, \ldots, B_N$이 공백으로 구분되어 주어진다.

$A$를 $2N-1$개의 정수로 이루어진 한 줄로, 공백으로 구분하여 출력한다.

같은 배열 $B$를 만드는 순열이 여러 개일 수 있다. 그 중 사전순으로 가장 앞서는 순열을 출력한다. 유효한 순열이 적어도 하나 존재함이 항상 보장된다.

• $1 \le N \le 100,000$
• 모든 $i$ ($1 \le i \le N$)에 대해 $1 \le B_i \le 2N-1$
• 접두사 중앙값이 $B$인 순열 $A$가 항상 존재함이 보장된다.