Дисквалiфiкацiя
Дисквалiфiкацiя
Однiєї ночi Семовi приснився страшний сон. У ньому Сема переслiдувала перестановка з n чисел, яка голосно i розбiрливо щось говорила про якусь олiмпiаду з програмування.
Пiсля того, як Сем подiлився цим сном з Юрою, вони разом переглянули книжку про тлумачення снiв, в якiй вичитали, що такий сон може означати лише одне — сильних команд на олiмпiадi буде рiвно стiльки, скiльки iнверсiй було в перестановцi. Нагадаємо, що iнверсiєю в перестановцi називається така пара iндексiв i та j, що i < j та pi
> pj
.
Оскiльки iнверсiй в перестановцi було чимало, Сем зрозумiв, що так дiла не буде. Використовуючи свої надприроднi дiбностi, Сем може повернутися в цей сон i дещо модифiкувати перестановку, так щоб мiнiмiзувати кiлькiсть сильних команд на олiмпiадi. Сем має час лише на k операцiй, i за одну операцiю вiн може помiняти мiсцями будь-якi два сусiднi елементи перестановки.
Допоможiть Семовi мiнiмiзувати кiлькiсть сильних команд на олiмпiадi — знайдiть послiдовнiсть з не бiльше нiж k операцiй, яка мiнiмiзує кiлькiсть iнверсiй в заданiй перестановцi.
Формат вхiдних даних
Перший рядок мiстить два цiлi числа n та k (**1 ⩽ n; k ⩽ 105
**) — кiлькiсть чисел у перестановцi та кiлькiсть операцiй, якi може зробити Сем.
Другий рядок мiстить n цiлих чисел p1
; p2
; : : : ; pn
(**1 ⩽ pi
⩽ n**). Гарантується, що всi числа рiзнi.
Формат вихiдних даних
У першому рядку виведiть цiле число m (**0 ⩽ m ⩽ k**) — кiлькiсть операцiй.
У кожному з наступних m рядках виведiть по два цiлi числа ai
та bi
(**1 ⩽ ai
; bi
⩽ n**) — iндекси двох сусiднiх елементiв перестановки, якi треба помiняти мiсцями.
Примiтка
У другому прикладi в перестановцi немає iнверсiй, тому можна нiчого не робити
3 2 3 2 1
2 3 2 2 1
3 2 1 2 3
0