최소 최대 카테시안 트리

길이가 $N$인 정수 수열 $A_0, A_1, \cdots, A_{N-1}$이 주어진다. 항의 번호는 $0$부터 $N-1$까지이며, 각 원소를 같은 번호의 정점의 값으로 생각하자. 다음 조건을 만족하는 최대 카테시안 트리와 최소 카테시안 트리를 구해 보자.

두 트리는 모두 이진 트리이며, 중위 순회하면 정점 번호가 $0, 1, \cdots, N-1$ 순서로 나타난다. 최대 트리에서는 부모의 값이 자식의 값 이상이고, 최소 트리에서는 부모의 값이 자식의 값 이하이다. 값이 같다면 번호가 작은 정점이 부모가 된다.

첫 번째 줄에 정수 $N$이 주어진다. $(0\le N\le100\,000)$

두 번째 줄에 정수 $A_0, A_1, \cdots, A_{N-1}$이 공백으로 구분되어 주어진다. $(-2^{63}\le A_i<2^{63})$ $N=0$이면 이 줄은 빈 줄이다.

첫 번째 줄부터 $N$개의 줄에 걸쳐 최대 트리의 각 정점의 왼쪽 자식 번호와 오른쪽 자식 번호를 정점 번호 순서대로 공백으로 구분하여 출력한다.

그다음 줄부터 $N$개의 줄에 걸쳐 최소 트리도 같은 형식으로 출력한다.

없는 자식은 $-1$을 출력한다. $N=0$이면 아무것도 출력하지 않는다.