The Bugs

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 an ingenious choice of units) is a positive integer. The measurement system is recent, poorly tested, and prone to errors. The project management suspects it is full of bugs. Mother Mary also suspects it is full of bugs. Everybody cries: Help!

To identify and correct the bugs, they decided to take the sequence of measured concentrations and analyze all triplets that occur in the sequence.

A triplet is a sequence of three integers. Each triplet has a characteristic. The characteristic of a triplet $(x, y, z)$ is the triplet $(sgn(y - x), sgn(z - y), sgn(z - x))$, where $sgn(a)$ is -1, 0, or 1 when $a$ is negative, zero, or positive.

A triplet $(x_1, y_1, z_1)$ is smaller than $(x_2, y_2, z_2)$ if and only if the first nonzero value in $(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 equals the characteristic of $T$.

A measured triplet is a triplet that is a subsequence of the measurement sequence. Its elements appear in the sequence in the same order as in the triplet, but they do not need to be adjacent.

Before analysis, the measured triplets are grouped by their labels. The management wants to know the set of labels of all measured triplets in advance.

The first line contains one integer $N$ ($3 \le N \le 2 \cdot 10^5$), the number of measurements. The next line contains $N$ integers $x_1, x_2, \ldots, x_N$ ($1 \le x_i \le 10^9$), each representing one measurement.

Print all distinct labels of the measured triplets that can be obtained from the given sequence, in increasing order, one per line. Print each label with no spaces between its consecutive elements.