Your colleague at Hiitsburgh Inversion Innovation Technologies has come up with the following sorting algorithm:

// Sort an array. Initialize with low = 0 and high = len(array)
algorithm HiitSort(array, low, high)
    if high - low > 1
        pivot <- median(array[low], array[(low + high) / 2], array[high - 1])

        a <- low
        b <- high - 1
        loop
            while array[a] < pivot      // (*)
                a <- a + 1
            while array[b] > pivot      // (*)
                b <- b - 1
            if a >= b
                break loop
            swap(array[a], array[b])
            a <- a + 1
            b <- b - 1

        call HiitSort(array, low, a)
        call HiitSort(array, a, high)

Your colleague claims that their algorithm uses only O(n \log n) comparisons against the pivot in total. You are sceptical of this claim and want to prove them wrong. In particular, you want to find an array of n distinct elements such that the algorithm makes at least n^2 / 4 comparison operations against the pivot.

For the purposes of this exercise, we are only interested in the comparisons against the pivot, that is the comparisons executed on lines 9 and 11 of the code above (marked with (*) in the code).

The array is 0-indexed and the division operator rounds down. Function median returns the value that is the median of the three arguments; it does not count towards comparisons.

Input

The input contains a single integer n, the number of elements in the array.

Constraints

• 2 \le n \le 1000

Output

The output contains n distinct integers from range [1, n], the array to be sorted.

Example

Input:

3

Output:

1 2 3

Explanation: The array takes 7 operations to sort, which is more than 3^2 / 4 = 2 \frac{1}{4}.

Input:

5

Output:

1 2 4 3 5

Explanation: The array takes 17 operations to sort, which is more than 5^2 / 4 = 4 \frac{1}{4}.