Balkan OI '11 P3 - Medians

View as PDF

Submit solution


Points: 12 (partial)
Time limit: 0.3s
Memory limit: 64M

Problem type

Let A be a permutation of 1, 2, \dots, 2N-1.
We define the prefix medians of A as an array B with N elements: where B[i] is the median of A[1], A[2], \dots, A[2i-1].
Note: The median of a list of M numbers (where M is odd) can be found by sorting the numbers and picking the middle one.

Task

You are given N and the array B. You are asked to determine a permutation A whose prefix medians are precisely B.

Input Specification

The input contains 2 lines. The first line contains one integer, N. The second line describes B: N integers, separated by space.

Output Specification

The output should contain A: one line with 2N-1 integers separated by space. If there are multiple permutations A leading to the same input array B, you may output any one. In all test data, there will always be at least one solution.

Constraints

  • 1 \le A[i] \le 2N-1, for every i from 1 to 2N-1
  • 1 \le B[i] \le 2N-1, for every i from 1 to N
  • 1 \le N \le 100\,000
  • 60\% of the tests will have N \le 1\,000

Sample Input

5
1 3 3 4 5

Sample Output

1 9 3 2 4 8 7 5 6

Comments

There are no comments at the moment.