eolymp
bolt
Try our new interface for solving problems
Problems

Дисквалiфiкацiя

Дисквалiфiкацiя

Time limit 1 second
Memory limit 64 MiB

Одн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.

Input data

Перший рядок м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.

Output data

У першому рядку вивед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чого не робити

Examples

Input example #1
3 2
3 2 1
Output example #1
2
3 2
2 1
Input example #2
3 2
1 2 3
Output example #2
0
Source 2019-2020 ACM-ICPC, SEERC, 1/8 фiналу, 13 квiтня 2019 року