Anti-QuickSort
To sort a sequence of numbers is widely used quicksort - QuickSort. The following is a program that sorts an array a, using this algorithm.
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.
Although QuickSort is the fastest sorting on the average, there are tests in which she works very long. Evaluate the running time will be the number of comparisons with the array elements (ie, the aggregate number of comparisons in the first and second while). Required to write a program that generates a test in which quicksort make the greatest number of such comparisons.
Input
The first line is a single number N (1 ≤ N ≤ 70000).
Output
Print a permutation of the numbers from 1 to N, where QuickSort performs the maximum number of comparisons. If there are several permutations, to withdraw any of them.