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