시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 256 MB0000.000%

문제

Автоматизация и компьютеризация стремительно вторгаются во все сферы нашей жизни. Посудомоечные машины, бортовые компьютеры в автомобилях, электрические мухобойки — все эти приспособления в той или иной степени облегчают человеку стандартные привычные действия. В этой же задаче от вас потребуется автоматизировать еще одно привычное многим действие — перемешивание колоды карт.

Рассмотрим новую колоду карт, карты в которой имеют некоторую характеристику, которая представляет собой целое число от 1 до t. Будем называть ее достоинством карты, несколько карт в колоде могут иметь одно и то же достоинство.

Исходно карты в колоде отсортированы по неубыванию достоинства. Соответственно, первая карта в колоде имеет достоинство 1, а последняя — достоинство t. При этом достоинства двух соседних карт в колоде отличаются друг от друга не более, чем на один, и достоинство каждой следующей карты не меньше достоинства предыдущей.

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

Для перемешивания колоды используется устройство, которое способно выполнять действия следующего типа: для некоторых i и j взять карты, которые находятся на позициях с i-й по j-ю включительно и переместить их в конец колоды в том же порядке.

Вам необходимо написать программу, которая по описанию исходной колоды составит последовательность из минимального количества указанных действий, в результате выполнения которых колода окажется хорошо перемешанной.

입력

В первой строке содержится одно целое положительное число x — количество колод, которые необходимо отсортировать. Далее идут описания x колод.

Описание каждой колоды состоит из двух строк. В первой строке описания колоды находится целое положительное число n — количество карт в колоде. В следующей строке содержатся n натуральных чисел, описывающие достоинства карт в колоде. Первое число в такой строке всегда равно единице, каждое следующее не меньше предыдущего и отличается от него не более, чем на 1.

Суммарное количество карт во всех колодах во вводе не превышает 200000.

출력

Для каждой колоды, данной во вводе, выведите «-1», если перемешать ее, используя описанные в условии действия, невозможно. Если же алгоритм перемешивания существует, то в первой строке его описания выведите k — минимальное количество действий, которое требуется для перемешивания колоды. В следующих k строках выведите действия, каждое из которых описывается двумя числами i и j — позициями карт, ограничивающих отрезок, который необходимо переместить в конец.

예제 입력 1

2
8
1 1 2 2 3 3 4 4
6
1 1 1 1 2 3

예제 출력 1

2
2 3
4 5
-1