Для сортировки последовательности чисел широко используется быстрая сортировка -- \textit{\textbf{QSort}}. Ниже приведена программа, которая сортирует массив \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{QSort}} является самой быстрой сортировкий в среднем, существуют тесты, на которых она работает очень долго. Будем оценивать время работы алгоритма количеством сравнений, сделанных с элементами массива (т.е. суммарным количеством сравнений в первом и втором \textit{\textbf{while}}). Требуется написать программу, генерирующую тест, на котором быстрая сортировка сделает наибольшее число таких сравнений. \InputFile В первой строке находится единственное число \textbf{N} (\textbf{1} ≤ \textbf{N} ≤ \textbf{70000}). \OutputFile Вывести перестановку чисел от \textbf{1} до \textbf{N}, на которой быстрая сортировка выполнит максимальное число сравнений. Если таких перестановок несколько, вывести любую из них.