Ali is leading a field trip to Bourke Street so that the FIT1008 team can buy some new whiteboard markers for their classes. But, as usual, the university is claiming it is out of money and needs to cut costs.

Today just so happens to be the Whiteboarding Holiday International Trade Event, so one side of Bourke Street is lined with whiteboard marker stalls, all selling various exotic colours and styles.

Because of the cost limitations, the university has ruled that the team can only buy markers from a stall if its markers are "a good deal". Markers are "a good deal" if their price is strictly cheaper than the prices at both the stall to the left and the stall to the right. As such, the team can never buy markers from the very first or very last stall on the street.

But! The university doesn't know that Ali is good friends with the people who run W.H.I.T.E., and he has control over which stall goes where! Ali would like to arrange the stalls so that the team can buy as many whiteboard markers as possible. Can you help him?

In order to pass the tests, your solution should have a time complexity of ~O(n\log(n))~.

Input

The first line contains a single integer ~n~ (~1 \leq n \leq 10^5~), the number of whiteboard marker stalls.

The second line contains ~n~ integers ~a_1, a_2, \ldots, a_n~ (~1 \leq a_i \leq 10^9~), the marker prices at each stall.

Output

On the first line, print the maximum number of markers that Ali and the team can purchase.

On the second line, print an ordering of the ~n~ prices that allows Ali and the team to achieve this maximum. If there are multiple valid orderings, you may print any of them.

Example 1

Input

7
1 3 2 2 4 5 4

Output

3
3 1 4 2 4 2 5

Ali and the team can buy from the stalls with prices 1, 2 and 2, because each of them is "a good deal". There is no possible arrangement where Ali can buy 4 markers.

Example 2

Input

6
2 3 3 3 3 3

Output

1
3 2 3 3 3 3

A stall with price 3 can never be "a good deal", since at least one of its neighbours will also have price 3 (or it will be at the end of the street). Only the stall with price 2 can be bought from.