Чтобы победить бога войны Ареса, Кратос должен добраться до ящика Пандоры, который может наделить своего владельца поистине божественной силой. К несчастью для спартанца, ящик находится в глубинах храма Пандоры, а на пути до храма встречается $$$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