Дискваліфікація#8778

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

1 секунда

64 мегабайти

Дуже легка

Однієї ночі Семові приснився страшний сон. У ньому Сема переслідувала перестановка з $n$ чисел, яка голосно і розбірливо щось говорила про якусь олімпіаду з програмування.

Після того, як Сем поділився цим сном з Юрою, вони разом переглянули книжку про тлумачення снів, в якій вичитали, що такий сон може означати лише одне — сильних команд на олімпіаді буде рівно стільки, скільки інверсій було в перестановці. Нагадаємо, що інверсією в перестановці називається така пара індексів $i$ та $j$ , що $i < j$ i < j та $p_{i} > p_{j}$ p_i > p_j.

Оскільки інверсій в перестановці було чимало, Сем зрозумів, що так діла не буде. Використовуючи свої надприродні здібності, Сем може повернутися в цей сон і дещо модифікувати перестановку, так щоб мінімізувати кількість сильних команд на олімпіаді. Сем має час лише на $k$ операцій, і за одну операцію він може поміняти місцями будь-які два сусідні елементи перестановки.

Допоможіть Семові мінімізувати кількість сильних команд на олімпіаді — знайдіть послідовність з не більше ніж $k$ операцій, яка мінімізує кількість інверсій в заданій перестановці.

Вхідні дані

Перший рядок містить два цілих числа $n$ та $k$ ( $1 \leq n; k \leq 1 0^{5}$ 1 \leq n;\ k \leq 10^5) — кількість чисел у перестановці та кількість операцій, які може зробити Сем.

Другий рядок містить $n$ цілих чисел $p_{1}, p_{2}, \dots, p_{n}$ p_1,\ p_2,\ \dots,\ p_n ( $1 \leq p_{i} \leq n$ 1 \leq p_i \leq n). Гарантується, що всі числа різні.

Вихідні дані

У першому рядку виведіть ціле число $m$ ( $0 \leq m \leq k$ 0 \leq m \leq k) — кількість операцій.

У кожному з наступних $m$ рядків виведіть по два цілих числа $a_{i}$ a_i та $b_{i}$ b_i ( $1 \leq a_{i}, b_{i} \leq n$ 1 \leq a_i,\ b_i \leq n) — індекси двох сусідніх елементів перестановки, які треба поміняти місцями.

Приклади

Приклад 1

Приклад 2

Примітка

У другому прикладі в перестановці немає інверсій, тому можна нічого не робити.