Pandora's Box#9065
To defeat the god of war Ares, Kratos must reach the Pandora's Box, an artifact that grants its wielder truly divine power. However, the path to this mighty relic lies through the Temple of Pandora, hidden deep within an ancient gorge. On his way to the temple, Kratos must cross mountains, where the height of the -th mountain is a_i meters.
There is only one thing in this world that even the mighty Kratos fears — height. He never jumps down: steep drops frighten the Spartan. However, he possesses a divine gift — in a single action, he can equalize the height of all mountains on a segment from to , if a_i = a_j. After using this power, all mountains from to (inclusive) will have height a_i.
To reach the Temple of Pandora, Kratos must use his power so that the heights along the entire path never decrease, that is, the following condition must be satisfied: a_i \le a_{i+1} for all i = 1, 2, ..., n - 1.
Kratos is in a hurry and does not want to attract Ares' attention, so he must minimize the number of times he uses his power. Help the Spartan reach his goal by performing the minimum possible number of equalizations.
In the first line, an integer n~(1 \le n \le 10^6) is given — the number of mountains on the way to the temple.
In the second line, integers a_i~(1 \le a_i \le 10^6) are given — the heights of the mountains.
In the first line, print the minimum number of actions that Kratos needs to perform so that the path to the temple becomes non-decreasing.
Then print lines, each containing two integers — the bounds of the segment and r~(1 \le l \le r \le n) that Kratos must equalize.
The actions should be printed in the order in which Kratos must perform them.
If there is no solution, print .
Example 1
Example 2