Problem D
Counting Staircases

Umi’s Flags

Umi Matsuzaki is raising signal flags to wish sailors good luck. She has $N$ flags with different heights. Her $N$ flags are represented by distinct integers $a_1, a_2, a_3, \dotsc , a_N$, where $a_i$ corresponds to the height of the $i$th flag.

Umi realizes that her signal flags are especially easy to see when they form patterns known as “staircases.” Umi knows a special width $M$. Then, define a “staircase” as a sequence of $2M-1$ flags such that the first $M$ flag heights form an increasing sequence and the last $M$ flag heights form a decreasing sequence. Formally, a staircase is a sequence of $2M - 1$ flags whose heights are $b_1, b_2, \dotsc , b_{2m-1}$, where $b_1 < b_2 < \dotsc < b_m$ and $b_m > b_{m+1} > b_{m+2} \dotsc > b_{2m-1}$.

Umi can rearrange her $N$ flags in any order. She notices that there may be groups of consecutive $2M -1$ flags in her ordering that form staircases. Compute the maximum number of staircases possible after considering all rearrangements of her $N$ flags. Also, give an ordering of Umi’s flags that produces this maximum number of staircases.

Input

The first line of input contain two space-separated integers $N \: (3 \leq N \leq 200\, 000)$, the number of flags Umi owns, and $M \: (2 \leq M \leq \lceil \frac{N}{2} \rceil )$, denoting that a staircase must consist of $2M - 1$ flags. The second line of input contains $N$ space-separated integers $a_1, a_2, a_3, \dotsc , a_N$ where $-10^5 \leq a_i \leq 10^5$. Each $a_i$ represents the height of the $i$-th flag, and all $a_i$ are distinct.

Output

The first line of output should contain the maximum amount of staircases possible in an ordering of Umi’s $N$ flags. The second line of output should contain $N$ space-separated integers, where the $i$-th integer corresponds to the height of the $i$-th flag in an optimal ordering of Umi’s flags. If there are multiple optimal orderings, you may output any such ordering.

8 2
-5 7 1 4 -3 6 2 11

3
-5 7 1 6 -3 4 2 11