## Balkan OI '11 P3 - Medians

View as PDF

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 be a permutation of .
We define the prefix medians of as an array with elements: where is the median of .
Note: The median of a list of numbers (where is odd) can be found by sorting the numbers and picking the middle one.

You are given and the array . 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, . The second line describes : integers, separated by space.

#### Output Specification

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

#### Constraints

• , for every from to
• , for every from to
• of the tests will have

#### Sample Input

5
1 3 3 4 5

#### Sample Output

1 9 3 2 4 8 7 5 6