Cartesian tree
You are given a set of pairs (a_i, b_i), and your task is to construct a Cartesian tree where the i-th node has keys (a_i, b_i). The nodes with key a_i should form a binary search tree, while the nodes with key b_i should form a heap.
Input
The first line contains the integer N, representing the number of pairs. This is followed by N pairs (a_i, b_i), where 1 ≤ N ≤ 50000. Each pair satisfies |a_i|, |b_i| ≤ 30000. Additionally, a_i ≠ a_j and b_i ≠ b_j for all i ≠ j.
Output
If it is possible to construct a Cartesian tree with these keys, print YES on the first line. Otherwise, print NO. If the answer is YES, follow it with N lines, each describing a node. Each node's description consists of three numbers: the index of the parent, the index of the left child, and the index of the right child. Use 0 to indicate the absence of a parent or child. If multiple valid trees exist, you may output any one of them.