To sort a sequence of numbers is widely used quicksort - \textit{\textbf{QuickSort}}. The following is a program that sorts an array \textbf{a}, using this algorithm. \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.}} Although \textit{\textbf{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 \textit{\textbf{while}}). Required to write a program that generates a test in which quicksort make the greatest number of such comparisons. \InputFile The first line is a single number \textbf{N} (\textbf{1} ≤ \textbf{N} ≤ \textbf{70000}). \OutputFile Print a permutation of the numbers from \textbf{1} to \textbf{N}, where QuickSort performs the maximum number of comparisons. If there are several permutations, to withdraw any of them.