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

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

Чтобы добраться до храма Пандоры, спартанцу требуется применить свой волшебный навык к некоторым отрезкам гор так, чтобы ему никогда не пришлось спускаться вниз, то есть выполнялось бы условие ai ≤ ai+1.

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

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

В первой строке дано количество гор n (1 ≤ n ≤ 106) на пути к храму Пандоры. Во второй строке дано n целых чисел ai (1 ≤ ai ≤ 106) - высоты гор.

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

В первой строке выведите минимальное количество действий p, которое нужно совершить Кратосу, чтобы добраться до храма Пандоры. В каждой из последующих p строк выведите два числа l и r - границы очередного отрезка гор, с которым нужно совершить действие по уравниванию. Действия выводите в том порядке, в котором их должен совершать Кратос. Если решения нет, в единственной строке выведите "-1".