Cartesian Tree Visualization

Rene Descartes was not only a famous philosopher, his other well-known hobby was gardening.

He is planting an orchard consisting of N fruit trees, all of different heights - and all of them along the road, in a straight line - so they could be enumerated say from 1 to N. Once he've been sleeping in this garden after laborious work and in a dream he was visited by large delegation of the Easter Bunnies, each of them querying something like "Which is the smallest tree in range between L-th and R-th".

Being able to answer such a question without iterating over all the trees in the range is the motivation for curious data structure, named Cartesian Tree after Descartes (his Latin pen-name). He never knew of it, but it doesn't matter. This structure may be useful in several whimsical puzzles, but being unable to come up with some really intriguing, we this time simply ask you to construct such a tree. If done correctly, you'll see visualisation of it above.

Cartesian Tree Description

In a simplest form it's built from an unordered array of values. The root element is the minimal one. Every element has left and right branch (so it is again binary tree). These branches lead to sub-trees built from sub-arrays - slices to left and right from the minimal element in the same manner. So it is recursive. Regard array 3 8 1 5 for example. It's minimal element is 1, then left sub-array is 3 8 and right one is 5. Among the left the next minimal is 3 and remaining 8 is the right sub-array of it.

    +------1-----+
    |            |
   -3---+       -5-
        |
       -8-

So all the "upper" elements are smaller then those below - it is the property of the Cartesian Tree. Falling into the left or right branch, on contrary, doesn't depend on value of the element, but on its index. The more general description of the tree regards elements as pairs (X, Y) where Y is the value (weight or priority) according to which elements hang higher or lower, while X is the coordinate determining left-right relation. In that regard the structure is two-dimensional and can be used in geometric context. Also due to this 2d-nature it is actually called "Cartesian" - the tree could be directly plotted on a cartesian plane.

Note: there is more than one way to construct the tree, recursive one is not the most elegant - but result of course is always the same.

Problem Statement

For an array of numbers, please build a tree according to the description above. The result of this building should be a list of lines to be plotted on a digital canvas. Each line is described by 4 values x1 y1 x2 y2.

Input Data provide the length of array N in the first line, the next line contains N integer values for this array. Let's agree indices (which are also X coordinates) are 1-based.

Answer please output the coordinates for line segments representing branches of a tree. There should be N-1 lines obviously, in every line there are expected 4 values - couple for start of the segment and couple of the end. You'll see Y is in range roughly 0 .. 300 so to make tree look "wide" enough multiplite all X coordinates by 10 please. If the output format is correct, the visualisation of a tree is automatically created in the canvas above.

Example

input:
4
30 80 10 50

answer:
30 10 10 30
30 10 40 50
10 30 20 80