Background

This problem is translated from CERC 2019 “The Bugs”.

Problem Description

A submarine painted in bright plastic lemon color is investigating the depth of the ocean and measuring the concentration of plastic yocto particles in the water. Each measurement (thanks to a clever choice of units) is a positive integer.

The measurement system is state-of-the-art, barely tested, and prone to errors. The project management suspects it is full of bugs. They find themselves in trouble. Mother Mary also suspects it is full of bugs. Everyone is shouting: help!

To find and fix these bugs, they gathered and decided to take the sequence of concentration measurements and analyze all triples that occur in the measurement sequence.

• A triple is a sequence of three integers.
• Each triple is associated with its signature triple.
• The signature triple of a triple $(x, y, z)$ is $(\text{sgn}(y-x), \text{sgn}(z-y), \text{sgn}(z-x))$. For a negative, zero, or positive value of $x$, the function $\text{sgn}(x)$ equals $-1$, $0$, or $1$, respectively, i.e. $\text{sgn}(x)=\begin{cases}0&x=0\\\dfrac{x}{|x|}&x\ne 0\end{cases}$.
• A triple $(x_1, y_1, z_1)$ is smaller than a triple $(x_2, y_2, z_2)$ if and only if the first non-zero value in $(x_1-x_2, y_1-y_2, z_1-z_2)$ is negative.
• The label triple of a triple $T$ is the smallest triple whose values are all positive and whose signature triple is equal to the signature triple of $T$.

A measured triple is a triple that is a subsequence of the measurement sequence. That is, the elements of the triple appear in the measurement sequence in the same order as in the triple, but they do not have to be consecutive in the sequence.

Before analyzing them, the measured triples are grouped by their label triples. The management wants to know in advance the set of label triples of all measured triples.

Input Format

The first line contains an integer $N\ (3\le N\le 2\times 10^5)$, the length of the measurement sequence.

The second line contains $N$ integers $x_1, x_2, x_N\ (1\le x_i\le 10^9)$, representing the measurement sequence.

Output Format

Output, in increasing order, all distinct label triples of all measured triples that can be obtained from the given measurement sequence, one per line. When outputting a label triple, there should be no spaces between consecutive elements.

5
1 2 3 4 5

123

6
5 4 9 1 7 4

121
132
211
212
213
231
312
321

Hint

Translated by ChatGPT 5