K-çeşidləmə

Çeşidləmə məsələsi, verilmiş ədədlər massivini (və ya digər obyektləri) artan və ya azalan qaydada sıralamaqdan ibarətdir. Bu məsələnin bir çox variantları mövcuddur və bir çoxunda çox effektiv alqoritmlər var. Bu alqoritmlərin mühüm parametrlərindən biri, massiv elementlərinin dəyişdirilmə sayıdır ki, bu da sıralama üçün zəruridir.

Biz burada $k$-çeşidləmə adlandırılan çeşidləmə variantını nəzərdən keçirəcəyik. Bu variantda bir əməliyyatla (adlandırılan $k$-dəyişmə) massivdəki iki elementin yerlərini dəyişmək icazə verilir, bu elementlərin indeksləri tam olaraq $k$ fərqlənir. Məsələn, əgər başlanğıc massiv [$6$, $10$, $4$, $1$, $2$] şəklindədirsə və $k$ = $3$-dürsə, bu massiv iki əməliyyatla artan qaydada sıralana bilər (birinci dəyişmədən sonra massiv [$1$, $10$, $4$, $6$, $2$] şəklində olacaq, ikinci dəyişmədən sonra isə [$1$, $2$, $4$, $6$, $10$]).

Verilmiş tam ədədlər massivi $a_1$, ..., $a_n$. Sizin vəzifəniz bu massivi artan qaydada sıralamaq üçün lazım olan minimal $k$-dəyişmələrin sayını müəyyən etməkdir.

Giriş məlumatları

Birinci sətir tam ədəd $n$ ($1$ ≤ $n$ ≤ $300$) ehtiva edir. İkinci sətir $n$ tam ədəd $a_1$, ..., $a_n$ ($1$ ≤ $a_i$ ≤ $10^9$ hər bir $i$ üçün $1$-dən $n$-ə qədər) ehtiva edir. Üçüncü sətir tam ədəd $k$ ($1$ ≤ $k$ ≤ $n$ - $1$) ehtiva edir.

Çıxış məlumatları

Əgər verilmiş massiv təsvir edilən tip əməliyyatlarla artan qaydada sıralana bilirsə, sıralama üçün lazım olan minimal $k$-dəyişmələrin sayını çıxarın. Əks halda, bir ədəd $-1$ çıxarın.

Nümunələr