Дисквал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 та p[i] > p[j].
Оск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 числа n та k (1 ⩽ n; k ⩽ 10^5) — кiлькiсть чисел у перестановцi та кiлькiсть операцiй, якi може зробити Сем.
Другий рядок мiстить n цiлих чисел p[1]; p[2]; : : : ; p[n] (1 ⩽ p[i] ⩽ n). Гарантується, що всi числа рiзнi.
Вихідні дані
У першому рядку виведiть цiле число m (0 ⩽ m ⩽ k) — кiлькiсть операцiй.
У кожному з наступних m рядках виведiть по два цiлi числа a[i] та b[i] (1 ⩽ a[i]; b[i] ⩽ n) — iндекси двох сусiднiх елементiв перестановки, якi треба помiняти мiсцями.
####Примiтка
У другому прикладi в перестановцi немає iнверсiй, тому можна нiчого не робити