Гарний масив#350

Гарний масив

1 секунда
256 мегабайтів
Середня

Масив називається красивим, якщо всі a_i-a_{i-1} (2 \leq i \leq n) є різними.

Наприклад, [1, 3, 2, 9] і [8, 4, 6, 9] є красивими, а [1, 2, 3, 9] і [1, 5, 5, 9] — ні.

Послідовність цілих чисел b_1, b_2, \dots, b_n називається перестановкою послідовності c_1, c_2, \dots, c_n, якщо кількість кожного унікального числа у цих масивах однакова. Наприклад, [1, 5, 3, 4, 2] є перестановкою [5, 2, 1, 4, 3], а [1, 3, 3, 5] є перестановкою [3, 5, 1, 3]. Проте [1, 3, 4] не є перестановкою [2, 3, 4] (вона не містить , які повинні з'явитись у послідовності, і має , які не повинні з'явитись).

Сакурако отримала масив. Вона хоче знайти приклад красивої перестановки заданого масиву.

Вхідні дані

Перший рядок містить одне ціле число (2\le n\le 2\cdot 10^5) — довжина масиву.

Другий рядок містить цілих чисел a_1, a_2, \dots, a_n (1\le a_i\le 10^9) — елементи масиву.

Гарантовано, що всі числа в масиві різні. Також гарантовано, що відповідь існує.

Вихідні дані

Виведіть гарний масив (який є перестановкою початкового масиву) в одному рядку. Якщо є кілька рішень, виведіть будь-яке.

Приклади

Приклад 1

Loading
Loading

Приклад 2

Loading
Loading

Примітка

У першому прикладі масив [3, 5, 4, 1, 2] є гарним, оскільки якщо ми візьмемо a_i-a_{i-1} для всіх , отримаємо:

  • 5-3=2;

  • 4-5=-1;

  • 1-4=-3;

  • 2-1=1.

Як ми бачимо, всі числа різні.

У другому прикладі масив [4, 2, 3] є гарним, оскільки якщо ми візьмемо a_i-a_{i-1} для всіх , отримаємо:

  • 2-4=-2;

  • 3-2=1.

Як ми бачимо, всі числа різні.

Оцінювання

Ви отримаєте щонайменше балів, якщо ваш розв'язок спрацює правильно для n\le 10.

Ви отримаєте не менше балів, якщо ваш розв'язок буде правильним для n\le 1000.