Для сортировки последовательности чисел широко используется быстрая сортировка – QSort. Ниже приведена программа, которая сортирует массив 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 a[j] > m do dec(j);
                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.

Хотя QSort является самой быстрой сортировкой в среднем, существуют тесты, на которых она работает очень долго. Будем оценивать время работы алгоритма количеством сравнений, сделанных с элементами массива (т.е. суммарным количеством сравнений в первом и втором while). Требуется написать программу, генерирующую тест, на котором быстрая сортировка сделает наибольшее число таких сравнений.

Входные данные

В первой строке находится единственное число N (1 ≤ N ≤ 70000).

Выходные данные

Вывести перестановку чисел от 1 до N, на которой быстрая сортировка выполнит максимальное число сравнений. Если таких перестановок несколько, вывести любую из них.