접두사 중앙값

시간 제한1초메모리 제한128 MB

요약

1부터 2N-1까지의 순열에서 얻은 접두 중앙값 배열 B가 주어질 때, 같은 중앙값을 내는 순열 중 사전순으로 가장 작은 것을 복원한다.

문제

$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$ 를 만드는 순열이 여러 개일 수 있다. 그 중 사전순으로 가장 앞서는 순열을 출력한다. 유효한 순열이 적어도 하나 존재함이 항상 보장된다.