Сізге \(n\) бүтін саннан тұратын массив берілген.

Оның элементтерін әрбір \(i\) индексі үшін, мұнда \(2 \leq i < n\), \(i\)-ші элементтен оның сол жақ көршісіне дейінгі қашықтық \(i\)-ші элементтен оның оң жақ көршісіне дейінгі қашықтықтан үлкен болмайтындай етіп қайта орналастыру керек.

Формалды түрде, берілген массивтің \(p\) перестановкасын табу керек, мұнда \(|p_i - p_{i - 1}| \leq |p_i - p_{i + 1}|\) шарты әрбір \(2 \leq i < n\) үшін орындалуы тиіс.

Жауап әрқашан бар екенін дәлелдеуге болады.

Енгізу

Бірінші жолда бір бүтін сан \(n\) \((3 \leq n \leq 2 \cdot 10^5)\) — массивтегі элементтер саны беріледі.

Екінші жолда \(n\) бүтін сан \(a_1, a_2, \ldots, a_n\) \((1 \leq a_i \leq 10^9)\) — массив элементтері беріледі.

Шығару

\(n\) бүтін сан \(p_1, p_2, \ldots, p_n\) шығарыңыз — шартты қанағаттандыратын берілген массивтің перестановкасы.

Егер бірнеше дұрыс жауап болса, олардың кез келгенін шығаруға болады.

Мысалдар

Енгізу 1

4
8 4 1 2

Жауап 1

1 2 4 8

Енгізу 2

7
7 10 7 7 10 10 7

Жауап 2

7 7 10 7 10 7 10