A submarine painted in bright plastic lemon color is investigating ocean depths and measuring the concentration of plastic yoctoparticles in the water. Each measurement (due to ingenious choice of the units) is a positive integer.
The measurement system is very recent, poorly tested and prone to errors. The project man- agement suspects it is full of bugs. They find themselves in a time of trouble. Mother Mary also suspects it is full of bugs. Everybody cries: Help!
To identify and correct the bugs, they came together and decided to take the sequence of measured concentrations and analyze all triplets that occur in the sequence of measurements.
• A triplet is a sequence of three integers.
• Each triplet is associated with its characteristic.
• The characteristic of a triplet (x,y,z) is a triplet (sgn(y − x),sgn(z − y),sgn(z − x)). The value of the sgn(x) function is −1, 0 or 1 for negative, zero or positive value of x, respectively.
• A triplet (x 1 ,y 1 ,z 1 ) is smaller than triplet (x 2 ,y 2 ,z 2 ) if and only if the first nonzero value in the triplet (x 1 − x 2 ,y 1 − y 2 ,z 1 − z 2 ) is negative.
• The label of a triplet T is the smallest triplet whose values are all positive and whose characteristic is equal to the characteristic of T.
A measured triplet is a triplet which is a subsequence of the measurement sequence. That is, the elements of the triplet appear in the measurement sequence in the same order they appear in the triplet, but in the sequence they do not necessarily follow each other.
Before they are analyzed, the measured triplets are grouped according to their labels. The management wants to know in advance the set of labels of all measured triplets.
The first line contains one integer N (3 ≤ N ≤ 2·10 5 ), the number of measurements.
The next line contains N integers x 1 ,x 2 ,...,x N (1 ≤ x i ≤ 10 9 ), each representing one measurement.