e-olymp
favorite Saytın davamlılığını təmin etmək üçün sizin kəməyinizə ehtiyacımız vardır, ətrafli məlumat üçün bannerə klikləyin
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