Для сортировки последовательности чисел широко используется быстрая сортировка – QSort
. Ниже приведена программа, которая сортирует массив a
, используя данный алгоритм.
Хотя QSort
является самой быстрой сортировкой в среднем, существуют тесты, на которых она работает очень долго. Будем оценивать время работы алгоритма количеством сравнений, сделанных с элементами массива (т.е. суммарным количеством сравнений в первом и втором while
). Требуется написать программу, генерирующую тест, на котором быстрая сортировка сделает наибольшее число таких сравнений.
В первой строке находится единственное число N
(1 ≤ N ≤ 70000
).
Вывести перестановку чисел от 1 до N
, на которой быстрая сортировка выполнит максимальное число сравнений. Если таких перестановок несколько, вывести любую из них.