Одн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чого не робити