Cartesian Tree Construction

Given a permutation p of the integers from \(1\) to \(n\), construct its Cartesian tree. The tree should satisfy the following properties:

• The nodes are numbered \(1, 2, \dots, n\) and their keys satisfy the binary search tree property (i.e. an in-order traversal of the tree gives the nodes in increasing order).
• Each node \(i\) has a weight \(p_i\). The tree must also satisfy the min-heap property with respect to these weights, i.e. for every node, its weight is less than the weights of its children.

Your task is to build the Cartesian tree corresponding to the given permutation.

Once the tree is constructed, for each node \(i\) (\(1 \le i \le n\)) output three integers:

1. The index of its parent (or 0 if it has no parent).
2. The index of its left child (or 0 if there is no left child).
3. The index of its right child (or 0 if there is no right child).

Note: It is guaranteed that a unique Cartesian tree exists for a given permutation.

inputFormat

The first line contains a single integer \(n\) (\(1 \le n \le 10^5\)), the size of the permutation.

The second line contains \(n\) distinct integers \(p_1, p_2, \dots, p_n\) which form a permutation of \(1, 2, \dots, n\).

outputFormat

Output \(n\) lines. The \(i\)th line should contain three integers separated by spaces:

• The index of the parent of node \(i\) (or 0 if none).
• The index of the left child of node \(i\) (or 0 if none).
• The index of the right child of node \(i\) (or 0 if none).

sample

5
5 2 3 1 4

2 0 0
4 1 3
2 0 0
0 2 5
4 0 0