Anti-QuickSort
Sıralama üçün geniş istifadə olunan sürətli çeşidləmə alqoritmi - QuickSort. Aşağıda bu alqoritmdən istifadə edərək a massivini sıralayan proqram verilmişdir.
var a : array [1..N] of integer;
procedure QSort(left, right : integer);
var m, i, j, t : integer;
begin
m := a[(left+right) div 2];
i := left; j := right;
repeat
while a[i] < m do inc(i); {birinci while}
while a[j] > m do dec(j); {ikinci while}
if i <= j then
begin
t := a[i]; a[i] := a[j]; a[j] := t;
inc(i); dec(j);
end;
until i > j;
if j > left then QSort(left, j);
if i < right then QSort(i, right);
end;
begin
...
QSort(1, N);
end.
QuickSort orta hesabla ən sürətli sıralama alqoritmi olsa da, bəzi hallarda çox uzun müddət işləyə bilər. Alqoritmin iş vaxtını, massiv elementləri ilə müqayisələrin sayı ilə qiymətləndirəcəyik (yəni, birinci və ikinci while-da ümumi müqayisələrin sayı). Sürətli çeşidləmənin maksimum sayda belə müqayisələr edəcəyi testi yaradan proqram yazmaq lazımdır.
Giriş verilənləri
Birinci sətirdə tək bir ədəd N (1 ≤ N ≤ 70000) verilir.
Çıxış verilənləri
Sürətli çeşidləmənin maksimum müqayisə sayını yerinə yetirəcəyi 1-dən N-ə qədər olan ədədlərin bir permutasiyasını çıxarın. Əgər belə permutasiyalardan bir neçəsi varsa, onlardan birini çıxarın.