Alternativ Balansering

Några grupdat-studenter har just lärt sig att använda binära sökträd. Sökträden är ordnade så att för varje nod $i$ med ett värde $v_ i$ gäller att dess vänstra barn och alla noder i delträdet med det vänstra barnet som rot har ett värde strikt mindre än $v_ i$ och motsvarande för det högra barnet men med värden strikt större än $v_ i$. Tyvärr finns det alltid en risk att ett binärt sökträd blir obalanserat så att sökningen blir mindre effektiv.

Vi säger att ett binärträd är balanserat om det för varje nod gäller att djupet hos dess vänstra- och högra delträd skiljer sig med som mest 1. Att kunna balansera ett binärt sökträd är ingen enkel uppgift och därför inget krav i Grundläggande Programmering och Datalogi. För att ändå visa den potentiella effektiviteten hos ett binärt sökträd har föreläsaren valt att ge studenterna data på ett sådant sätt att trädet blir balanserat automatiskt.

Studenterna har skrivit ett program som läser in heltal och placerar dem i trädet i ordningen de läses in. Om trädet är tomt sätts ett värde in som roten. Om trädet inte är tomt hamnar det nya värdet som barn till en nod i trädet på ett sådant sätt att sökträdets egenskaper bevaras och platsen där värdet sätts in tidigare var tom. Givet en lista med heltal, ordna dem så att trädet blir balanserat. Det garanteras att alla tal är olika.

Input

Första raden innehåller ett heltal $n$ $(1 \le n \le 1000)$ - antalet heltal i listan. Sedan följer listan med $n$ heltal, $a_1, a_2, ..., a_ n$ $(0 \le a_ i \le 10^6)$. Alla tal är olika.

Output

Skriv ut n heltal - en permutation av talen i listan så att trädet blir balanserat. Om det finns flera lösningar, skriv ut vilken som helst.

Sample Input 1 Sample Output 1
7
1 2 3 4 5 6 7
4 2 1 3 6 5 7
Sample Input 2 Sample Output 2
3
15 22 8
15 22 8
Sample Input 3 Sample Output 3
8
5 15 9 8 13 17 3 1
8 3 1 5 13 9 15 17