버그

밝은 레몬색 플라스틱으로 칠해진 잠수함이 바다 깊은 곳을 조사하며 물속 플라스틱 요쿠토입자의 농도를 측정하고 있다. 각 측정값은 (단위를 영리하게 정한 덕분에) 양의 정수이다.

측정 시스템은 새로 만들어졌고 충분히 검증되지 않아 오류가 잦다. 프로젝트 관리팀은 시스템에 버그가 많다고 의심한다. Mother Mary도 같은 의심을 품고 있다. 모두가 도와달라고 외친다.

버그를 찾아내 고치려고, 측정 농도 수열에 나타나는 모든 세 수의 조합을 분석하기로 했다.

세 수의 조합은 정수 세 개로 된 수열이다. 각 조합에는 특성이 있다. 조합 $(x, y, z)$의 특성은 $(sgn(y - x), sgn(z - y), sgn(z - x))$이다. 여기서 $sgn(a)$는 $a$가 음수, 0, 양수일 때 각각 -1, 0, 1이다.

조합 $(x_1, y_1, z_1)$이 $(x_2, y_2, z_2)$보다 작은 것은, $(x_1 - x_2, y_1 - y_2, z_1 - z_2)$에서 처음으로 0이 아닌 값이 음수일 때뿐이다. 조합 $T$의 레이블은 모든 값이 양수이면서 특성이 $T$의 특성과 같은 조합 가운데 가장 작은 것이다.

측정 조합은 측정 수열의 부분수열인 조합이다. 원소들은 조합에 적힌 순서대로 수열에 나타나지만, 서로 인접할 필요는 없다.

분석에 앞서 측정 조합들을 레이블별로 묶는다. 관리팀은 모든 측정 조합의 레이블 집합을 미리 알고 싶어 한다.

첫째 줄에 정수 $N$($3 \le N \le 2 \cdot 10^5$)이 주어진다. 둘째 줄에는 $N$개의 정수 $x_1, x_2, \ldots, x_N$($1 \le x_i \le 10^9$)이 주어진다. 각 정수는 측정값 하나를 나타낸다.

주어진 수열에서 얻을 수 있는 측정 조합의 서로 다른 레이블을 오름차순으로 한 줄에 하나씩 출력한다. 각 레이블의 원소 사이에는 공백을 넣지 않는다.