Написать сортировку
Шелла N чисел со следующим шагом приращений (последовательность Седжвика, элементы берутся в обратном порядке): 1, 5, 19, 41, 109, 209, 505, 929, 2161, 3905, 8929, 16001, 36289, 64769...
В этой последовательности используются только первые k членов - inc[0], inc[1], ..., inc[k-1], где
k - наименьшее число, при котором 3*inc[k]>N.
Число элементов массива N вводится с клавиатуры.
Входные данные
В
первой строке записано натуральное число N (N <=
50 000).
В последующих строках содержится N целых чисел из отрезка [0, 1 000 000 ]. Числа разделены пробелами и/или символами конца строки.
Выходные данные
Программа должна записать в выходной поток натуральное число р, где р – число перестановок, совершаемое при сортировке входных данных. В данной задаче под термином "перестановка" понимается сдвиг одного элемента вправо (на расстояние, равное текущему инкременту).
Примеры входных и выходных данных
INPUT OUTPUT
5 8
23 54 17 0 9
8 12
65 12 76 32 68 21 90 44
Автор: Маклаков Г.В.
