eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Ящик Пандоры

Ящик Пандоры

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB

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

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

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

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

Вхідні дані

В первой строке дано количество гор n (1n10^6) на пути к храму Пандоры. Во второй строке дано n целых чисел a[i] (1a[i]10^6) - высоты гор.

Вихідні дані

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

Приклад

Вхідні дані #1
6
1 2 3 1 4 5
Вихідні дані #1
1
1 4
Вхідні дані #2
10
1 2 1 3 1 5 6 5 6 6
Вихідні дані #2
2
1 5
6 8
Джерело 2018 Цикл Интернет-олимпиад для школьников, вторая командная олимпиада сезона, базовая номинация, 20 октября, Задача D