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]