Ящик Пандоры
Чтобы победить бога войны Ареса, Кратос должен добраться до ящика Пандоры, который может наделить своего владельца поистине божественной силой. К несчастью для спартанца, ящик находится в глубинах храма Пандоры, а на пути до храма встречается n гор, высота i-й горы составляет a[i] метров.
Единственная вещь в мире, которую боится могущественный Кратос - высота. Именно поэтому он никогда не спускается и не прыгает вниз, огромные перепады высот пугают спартанца. Зато он очень хорошо прыгает и обладает божественным навыком: если высота i-й горы равна высоте j-й, то Кратос может за одно действие сделать все горы на отрезке с i по j включительно высотой a[i].
Чтобы добраться до храма Пандоры, спартанцу требуется применить свой волшебный навык к некоторым отрезкам гор так, чтобы ему никогда не пришлось спускаться вниз, то есть выполнялось бы условие a[i] ≤ a[i+1].
Кратос очень торопится и не хочет быть замеченным Аресом, поэтому не может слишком часто менять высоты гор. Помогите Кратосу добраться до храма Пандоры за минимальное количество действий.
Входные данные
В первой строке дано количество гор n (1 ≤ n ≤ 10^6) на пути к храму Пандоры. Во второй строке дано n целых чисел a[i] (1 ≤ a[i] ≤ 10^6) - высоты гор.
Выходные данные
В первой строке выведите минимальное количество действий p, которое нужно совершить Кратосу, чтобы добраться до храма Пандоры. В каждой из последующих p строк выведите два числа l и r - границы очередного отрезка гор, с которым нужно совершить действие по уравниванию. Действия выводите в том порядке, в котором их должен совершать Кратос. Если решения нет, в единственной строке выведите "-1".