e-olymp
favorite We need a little bit of your help to keep things running, click on this banner to learn more
Competitions

2018 Цикл Интернет-олимпиад для школьников

Pandora's Box

To defeat the god of war Ares, Kratos must get to the Pandora's box, which can endow its owner with truly divine power. Unfortunately for the Spartan, the box is in the depths of the Pandora's temple, and n mountains are found on the way to the temple, the height of the i-th mountain is ai meters.

The only thing in the world that the mighty Kratos fears is height. That is why he never goes down and does not jump down, huge differences in heights scare the Spartan. But he jumps very well and has a divine skill: if the height of the i - th mountain equals to the height of j - th, then Kratos can make all the mountains in a section from i to j in one action inclusive of height ai.

To get to the Pandora's temple, the Spartan needs to apply his magical skill to some sections of the mountains so that he never has to go down, that is, the condition aiai+1 should take place.

Kratos is in a hurry and does not want to be noticed by Ares, therefore he cannot change the heights of the mountains too often. Help Kratos get to the Pandora Temple in a minimal amount of action.

Input

First line contains the number of mountains n (1n106) on the way to the Pandora's temple. Second line contains n integers ai (1ai106) - the heights of the mountains.

Output

In the first line print the minimum number of actions p that Kratos needs to perform in order to get to the Pandora's Temple. In each of the following p lines print two numbers l and r - the boundaries of the next section of mountains with which you need to perform the adjustment action. Output the actions in the order in which they should be performed by Kratos. If there is no solution, in the single line print "-1".

Time limit 1 second
Memory limit 128 MiB
Input example #1
6
1 2 3 1 4 5
Output example #1
1
1 4
Input example #2
10
1 2 1 3 1 5 6 5 6 6
Output example #2
2
1 5
6 8
Source 2018 Cycle of Internet Olympiads for schoolchildren, second team season olympiad, Basic nomination, October 20, Problem D