Balkan OI '11 P3 - Medians

View as PDF

Submit solution

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

Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

Let A be a permutation of 1, 2, 3 \ldots, 2N - 1.
We define the prefix medians of A as an array B with N elements: where \mathrm B[i] is the median of \mathrm A[1], \mathrm A[2], \ldots, \mathrm 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.


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.


  • 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

1 3 3 4 5

Sample Output

1 9 3 2 4 8 7 5 6


There are no comments at the moment.