e-olymp
Məsələlər

Ящик Пандоры

Ящик Пандоры

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

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

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

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

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

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

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

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

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 128 MiB
Giriş verilənləri #1
6
1 2 3 1 4 5
Çıxış verilənləri #1
1
1 4
Giriş verilənləri #2
10
1 2 1 3 1 5 6 5 6 6
Çıxış verilənləri #2
2
1 5
6 8
Mənbə 2018 Цикл Интернет-олимпиад для школьников, вторая командная олимпиада сезона, базовая номинация, 20 октября, Задача D