Чтобы добраться зимой до офиса в Новосибирске нужно преодолеть n снежных гор, высота i-й горы составляет a_i метров.

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

Чтобы добраться до офиса, Сергею требуется применить свой навык к некоторым отрезкам гор так, чтобы ему никогда не пришлось спускаться вниз, то есть выполнялось бы условие a_i ⩽ a_i+1. Сергей очень торопится и не хочет тратить много сил, поэтому не может слишком часто менять высоты гор. Помогите Сергею добраться до офиса за минимальное количество действий.

Формат входных данных

В первой строке дано целое число n — количество гор на пути к офису (1 ⩽ n ⩽ 10⁶). Во второй строке дано n целых чисел a_i — высоты гор (1 ⩽ a_i ⩽ 10⁶).

Формат выходных данных

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

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

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

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

Пример