Problem C: Arrange Seats in a Round Table

Problem C: Arrange Seats in a Round Table

Time Limit: 2 Sec  Memory Limit: 128 MB
Submit: 2387  Solved: 223
[Submit][Status][Web Board]

Description

Suppose there are n students in CS203 DSAA, the height of each student is \(a_i (1 \leq i \leq n)\). You are asked to arrange these students to the seats (i.e., \(b_1, b_2, …, b_n\)) in a round table such that the minimum value, denoted by \(k\), of the medium height of every three students in consecutive seats (i.e., \(b_i\), \(b_{i\bmod n + 1}\), \(b_{(i + 1)\bmod n + 1}\)) is maximized.


Please print \(k\) and the height of the student in seats \(b_1, b_2, …, b_n\).

If it has more than one possible solution, print the height of the student in seats \(b_1, b_2, …, b_n\) with smallest lexicographical order. 


Input

There will be two lines.

The first line will be an integer \(n\).

The second line will be \(n\) integers \(a_1, a_2, ..., a_n\).

For all test cases, \(3\leq n\leq 10^6, 0\leq a_i\leq 10^9\).

Output

There will be two lines.

The first line prints the value of k

The second line prints the height of the student in seats \(b_1, b_2, …, b_n\).

Sample Input

6
6 5 4 3 2 1

Sample Output

3
1 3 4 2 5 6

HINT

You can find the definition of lexicographical
order at https://en.wikipedia.org/wiki/Lexicographic_order

[Submit][Status]