Pandora's Box

To defeat Ares, the god of war, Kratos must reach Pandora's box, which can grant its owner truly divine power. Unfortunately for the Spartan, the box lies in the depths of the Temple of Pandora, and $n$ mountains stand on the way to the temple. The height of the $i$-th mountain is $a_i$ meters.

The only thing the mighty Kratos fears is heights. That is why he never descends or jumps down, since large drops in height frighten him. He does jump very well, and he has a divine skill: if the height of the $i$-th mountain equals the height of the $j$-th, Kratos can make all mountains on the segment from $i$ to $j$ inclusive have height $a_i$ in a single action.

To reach the temple, Kratos must apply his skill to some segments so that he never has to go down, that is, the condition $a_i \le a_{i+1}$ holds. Kratos is in a hurry and does not want to be noticed by Ares, so he cannot change the heights too often. Help Kratos reach the temple with the minimum number of actions.

The first line contains an integer $n$, the number of mountains on the way to the temple ($1 \le n \le 10^6$).

The second line contains $n$ integers $a_i$, the heights of the mountains ($1 \le a_i \le 10^6$).

In the first line, print $p$, the minimum number of actions Kratos must perform to reach the temple.

In each of the next $p$ lines, print two numbers $l$ and $r$, the bounds of the segment for the next leveling action. Print the actions in the order Kratos must perform them.

If there is no solution, print -1 on a single line.