Diskvalifikasiya
Bir gecə Sem qorxulu bir yuxu gördü. Yuxuda Semə n ədədindən ibarət bir permutasiya göstərildi və bu permutasiya yüksək səslə hansısa proqramlaşdırma olimpiadası haqqında danışırdı.
Sem bu yuxunu Yura ilə paylaşdıqdan sonra, birlikdə yuxu yozumları kitabına baxdılar və belə bir yuxunun yalnız bir şey ifadə edə biləcəyini öyrəndilər — olimpiadada güclü komandaların sayı permutasiyadakı inversiyaların sayı qədər olacaq. Xatırladaq ki, permutasiyada inversiya, elə bir indekslər cütü i və j-dir ki, i < j və p[i] > p[j].
Permutasiyada çoxlu inversiyalar olduğuna görə, Sem başa düşdü ki, bu belə olmaz. Öz fövqəltəbii qabiliyyətlərindən istifadə edərək, Sem bu yuxuya qayıdıb permutasiyanı bir qədər dəyişdirə bilər ki, olimpiadada güclü komandaların sayını minimuma endirsin. Semin yalnız k əməliyyat üçün vaxtı var və bir əməliyyatla o, permutasiyanın istənilən iki qonşu elementini yerlərini dəyişə bilər.
Sema olimpiadada güclü komandaların sayını minimuma endirməkdə kömək edin — verilmiş permutasiyada inversiyaların sayını minimuma endirən ən çox k əməliyyat ardıcıllığını tapın.
Giriş formatı
Birinci sətir iki tam ədəd n və k (1 ⩽ n; k ⩽ 10^5) — permutasiyadakı ədədlərin sayı və Semin edə biləcəyi əməliyyatların sayını ehtiva edir.
İkinci sətir n tam ədəd p[1], p[2], ..., p[n] (1 ⩽ p[i] ⩽ n) ehtiva edir. Bütün ədədlərin fərqli olduğu təmin edilir.
Çıxış formatı
Birinci sətirdə tam ədəd m (0 ⩽ m ⩽ k) — əməliyyatların sayını çıxarın.
Növbəti m sətirdə hər birində iki tam ədəd a[i] və b[i] (1 ⩽ a[i], b[i] ⩽ n) — permutasiyanın yerlərini dəyişdirmək lazım olan iki qonşu elementin indekslərini çıxarın.
Qeyd
İkinci nümunədə permutasiyada inversiyalar yoxdur, buna görə də heç nə etmək lazım deyil.