Break the quicksort

A service accepts lists of numbers from users and sorts them with this function: quicksort with Hoare’s partition, where the pivot is the middle element of the piece. The function returns the number of comparisons made:

def quicksort(a):
    count = 0
    stack = [(0, len(a) - 1)]
    while stack:
        lo, hi = stack.pop()
        if hi <= lo:
            continue
        p = (lo + hi) // 2
        a[lo], a[p] = a[p], a[lo]
        x, i, j = a[lo], lo - 1, hi + 1
        while True:
            i += 1
            count += 1
            while a[i] < x:
                i += 1
                count += 1
            j -= 1
            count += 1
            while x < a[j]:
                j -= 1
                count += 1
            if i >= j:
                break
            a[i], a[j] = a[j], a[i]
        stack.append((j + 1, hi))
        stack.append((lo, j))
    return count

On random data it needs on the order of n log₂ n comparisons, and on already sorted data too. The owners of the service are sure it will always be so. Show that they are wrong: construct a permutation of the numbers from 1 to n on which the function makes at least ⌊n²/4⌋ comparisons.

Input

One number n (1 ≤ n ≤ 1000).

Output

n distinct numbers from 1 to n separated by spaces. If several permutations fit, print any.