Сломайте быструю сортировку

Сервис принимает от пользователей списки чисел и сортирует их вот этой функцией — быстрой сортировкой с разбиением Хоара, где опорным берётся средний элемент куска. Функция возвращает число сделанных сравнений:

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

На случайных данных ей хватает порядка n log₂ n сравнений, на уже отсортированных — тоже. Владельцы сервиса уверены, что так будет всегда. Покажите, что они ошибаются: составьте перестановку чисел от 1 до n, на которой функция сделает не меньше ⌊n²/4⌋ сравнений.

Вход

Одно число n (1 ≤ n ≤ 1000).

Выход

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