F. Красивые столблетки
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Для массива $$$b$$$ из $$$m$$$ целых чисел пара индексов $$$(l, r)$$$ ($$$l \lt r$$$) называется хорошей, если $$$b_l = b_r$$$ и не существует индекса $$$i$$$ ($$$l \lt i \lt r$$$), для которого $$$b_i \ge b_l$$$.

Будем говорить, что индекс $$$i$$$ покрыт хорошей парой $$$(l, r)$$$, если $$$l \le i \le r$$$.

Массив $$$b$$$ называется красивым, если каждый индекс покрыт хотя бы одной хорошей парой.

Вам дан массив $$$a$$$ из $$$n$$$ целых чисел. С ним можно выполнять следующую операцию: выбрать два целых числа $$$i$$$ и $$$x$$$ ($$$1 \le i \le n$$$, $$$1 \le x \le 10^9$$$) и присвоить $$$a_i = x$$$.

Найдите минимальное количество операций, необходимое, чтобы сделать массив красивым. Также выведите сами операции. Можно показать, что всегда можно сделать массив красивым, выполнив не более $$$n$$$ операций.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

В первой строке каждого набора входных данных находится одно целое число $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — длина массива $$$a$$$.

Во второй строке каждого набора входных данных находятся $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — массив $$$a$$$.

Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных выведите одно целое число $$$k$$$ ($$$0 \le k \le n$$$) — минимальное количество операций.

Затем выведите $$$k$$$ строк, описывающих операции в порядке их выполнения. Каждая из этих строк должна содержать два целых числа $$$i$$$ и $$$x$$$ ($$$1 \le i \le n$$$, $$$1 \le x \le 10^9$$$) — индекс и новое значение в соответствующей операции.

Если существует несколько оптимальных последовательностей операций, выведите любую из них.

Пример
Входные данные
5
3
1 2 3
8
5 3 2 5 1 7 9 9
5
1 1 1 1 1
8
1 2 3 4 4 3 2 1
2
1000000000 1000000000
Выходные данные
1
1 3
1
5 7
0
2
1 3
8 3
0
Примечание

В первом примере в массиве $$$a = [1, 2, 3]$$$ вообще нет хороших пар, поэтому он не является красивым. После операции с $$$i = 1$$$ и $$$x = 3$$$ массив становится равным $$$[3, 2, 3]$$$. Пара $$$(1, 3)$$$ хорошая, поскольку оба её крайних элемента равны $$$3$$$, а единственный элемент между ними равен $$$2 \lt 3$$$, поэтому она покрывает все три индекса.

Во втором примере в массиве $$$a = [5, 3, 2, 5, 1, 7, 9, 9]$$$ есть ровно две хорошие пары, $$$(1, 4)$$$ и $$$(7, 8)$$$, поэтому индексы $$$5$$$ и $$$6$$$ не покрыты. Операция с $$$i = 5$$$ и $$$x = 7$$$ превращает массив в $$$[5, 3, 2, 5, 7, 7, 9, 9]$$$: пары $$$(1, 4)$$$ и $$$(7, 8)$$$ по-прежнему хорошие, а новая хорошая пара $$$(5, 6)$$$ покрывает два оставшихся индекса.

В третьем примере массив уже красивый, поскольку $$$(i, i + 1)$$$ является хорошей парой для каждого $$$i$$$ от $$$1$$$ до $$$4$$$. Поэтому не требуется ни одной операции.