Для сортування послідовності чисел широко використовується швидке сортування - \textit{\textbf{QuickSort}}. Далі наведено програму, яка сортує массив \textbf{a}, використувуючи цей алгоритм. \textit{\textbf{var a : array \[1..N\] of integer;}} \textit{\textbf{procedure QSort(left, right : integer);}} \textit{\textbf{var m, i, j, t : integer;}} \textit{\textbf{begin}} \textit{\textbf{m := a\[(left+right) div 2\];}} \textit{\textbf{i := left; j := right;}} \textit{\textbf{repeat}} \textit{\textbf{while a\[i\] < m do inc(i); \{перший while\}}} \textit{\textbf{while a\[j\] > m do dec(j); \{другий while\}}} \textit{\textbf{if i <= j then}} \textit{\textbf{begin}} \textit{\textbf{t := a\[i\]; a\[i\] := a\[j\]; a\[j\] := t;}} \textit{\textbf{inc(i); dec(j);}} \textit{\textbf{end;}} \textit{\textbf{until i > j;}} \textit{\textbf{if j > left then QSort(left, j);}} \textit{\textbf{if i < right then QSort(i, right);}} \textit{\textbf{end;}} \textit{\textbf{begin}} \textit{\textbf{...}} \textit{\textbf{QSort(1, N);}} \textit{\textbf{end.}} Хоча \textit{\textbf{QuickSort}} є самим швидким сортуванням у середньому, існують тести, на яких воно працює дуже довго. Оцінювати час роботи алгоритму будемо кількістю порівнянь з елементами масиву (тобто сумарною кількістю порівнянь у першому і другому \textit{\textbf{while}}). Потрібно написати програму, яка генерує тест, на якому швидке сортування зробить найбільшу кількість таких порівнянь. \InputFile У першому рядку знаходиться єдине число \textbf{N} (\textbf{1} ≤ \textbf{N} ≤ \textbf{70000}). \OutputFile Вивести перестановку чисел від \textbf{1} до \textbf{N}, на якій швидке сортування виконає максимальне число порівнянь. Якщо таких перестановок декілька, вивести довільну з них.