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

Однажды ночью Семе приснился кошмар. В этом сне его преследовала перестановка из n чисел, которая громко и отчетливо говорила о какой-то олимпиаде по программированию.

Когда Сем рассказал об этом сне Юре, они вместе заглянули в книгу по толкованию снов и узнали, что такой сон может означать только одно: на олимпиаде будет ровно столько сильных команд, сколько инверсий в перестановке. Напомним, что инверсией в перестановке называется пара индексов i и j, таких что i < j и p[i] > p[j].

Поскольку инверсий в перестановке оказалось много, Сем понял, что так дело не пойдет. Используя свои сверхъестественные способности, Сем может вернуться в этот сон и немного изменить перестановку, чтобы минимизировать количество сильных команд на олимпиаде. У него есть время только на k операций, и за одну операцию он может поменять местами любые два соседних элемента перестановки.

Помогите Сему минимизировать количество сильных команд на олимпиаде — найдите последовательность из не более чем k операций, которая минимизирует количество инверсий в данной перестановке.

Формат входных данных

Первая строка содержит два целых числа n и k (1 ⩽ n; k ⩽ 10^5) — количество чисел в перестановке и количество операций, которые может сделать Сем.

Вторая строка содержит n целых чисел p[1], p[2], ..., p[n] (1 ⩽ p[i] ⩽ n). Гарантируется, что все числа различны.

Формат выходных данных

В первой строке выведите целое число m (0 ⩽ m ⩽ k) — количество операций.

В каждой из следующих m строк выведите по два целых числа a[i] и b[i] (1 ⩽ a[i], b[i] ⩽ n) — индексы двух соседних элементов перестановки, которые нужно поменять местами.

Примеры

Примечание

Во втором примере в перестановке нет инверсий, поэтому можно ничего не делать.