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 ai ≤ ai+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 (1 ≤ n ≤ 106) on the way to the Pandora's temple. Second line contains n integers ai (1 ≤ ai ≤ 106) - 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".