Ящик Пандоры
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Чтобы победить бога войны Ареса, Кратос должен добраться до ящика Пандоры, который может наделить своего владельца поистине божественной силой. К несчастью для спартанца, ящик находится в глубинах храма Пандоры, а на пути до храма встречается $$$n$$$ гор, высота $$$i$$$-й горы составляет $$$a_i$$$ метров.

Единственная вещь в мире, которую боится могущественный Кратос — высота. Именно поэтому он никогда не спускается и не прыгает вниз, огромные перепады высот пугают спартанца. Зато он очень хорошо прыгает и обладает божественным навыком: если высота $$$i$$$-й горы равна высоте $$$j$$$-й, то Кратос может за одно действие сделать все горы на отрезке с $$$i$$$ по $$$j$$$ включительно высотой $$$a_i$$$.

Чтобы добраться до храма Пандоры, спартанцу требуется применить свой волшебный навык к некоторым отрезкам гор так, чтобы ему никогда не пришлось спускаться вниз, то есть выполнялось бы условие $$$a_i \le a_{i+1}$$$.

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

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

В первой строке дано целое число $$$n$$$ — количество гор на пути к храму Пандоры ($$$1 \le n \le 10^6$$$).

Во второй строке дано $$$n$$$ целых чисел $$$a_i$$$ — высоты гор ($$$1 \le a_i \le 10^6$$$).

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

В первой строке выведите $$$p$$$ — минимальное количество действий, которое нужно совершить Кратосу, чтобы добраться до храма Пандоры.

В каждой из последующих $$$p$$$ строк выведите два числа $$$l$$$ и $$$r$$$ — границы очередного отрезка гор, с которым нужно совершить действие по уравниванию.

Действия выводите в том порядке, в котором их должен совершать Кратос.

Если решения нет, в единственной строке выведите «-1».

Примеры

Входные данные
6
1 2 3 1 4 5
Выходные данные
1
1 4
Входные данные
10
1 2 1 3 1 5 6 5 6 6
Выходные данные
2
1 5
6 8