It was the middle of the 23rd century. Alien creatures suddenly came out from hyperspace
and attacked the Twenty-fifth colonization mission just when all its
members gathered in a concert of one of the most popular singers in the
whole Galaxy. Nearly a third of all mission members died during
the ensuing panic and chaos.
Since then control of hyperspace has become one of the highest priorities
of the Defense Forces. Automatic drones with hyperspace field vibration amplitude sensors
were sent to the farthest corners of the inhabited part of the Galaxy. However,
collecting data from them turned out to be a quite complicated technical problem.
The point is that a huge amount of energy is required to transmit data at such distances
without distortion. Even the usage of intermediary retransmitters doesn’t improve the
situation much. However, engineers managed to find a sufficiently elegant solution.
The retransmitter sends not the measured value, but an absolute
value of the difference between the measured value and some reference value, which is imprinted in the
memory of this retransmitter. These reference numbers are chosen in such a way that for the
normal vibration level detected by sensor the final retransmitter in chain should send
a number that is close to zero. So, when the final retransmitter sends the number that is strictly
greater than one, the hyperspace disturbance is assumed to have happened. Security
experts are interested how reliable the system of k retransmitters is, and what range of
sensor readings will be interpreted as a calm state of hyperspace field. You are delegated to
study this question.
The first line contains an integer k that is the total number of retransmitters (1 ≤ k ≤ 10).
The second line contains integers a1, …, ak that are the
reference values recorded in the memory of retransmitters in the order the signal
follows from the hyperspace field sensor to the receiver on the
scout ship (−1000 ≤ ai ≤ 1000).
In the first line output the integer n that is the amount of segments in answer.
In the i'th of the following n lines output integers li ≤ ri that are the bounds of the i'th segment.
The segments must be output in the ascending order of coordinates and without mutual intersections.
0 4 2
Problem Author: Alexander Ipatov
Problem Source: Ural Championship 2012