<|instruction|>
Solve the below problem. The solution should start with an abridged problem statement. Then key observations. Then full solution based on the observations. Then C++ and Python implementations with comments.

155. Cartesian Tree
time limit per test: 0.25 sec.
memory limit per test: 65536 KB
input: standard input
output: standard output



Let us consider a special type of binary search trees, called cartesian trees. Recall that a binary searchtree is a rooted ordered binary tree, such that for its every node x the following condition is satisfied: each node in its left subtree has the key less than the key of x, and each node in its right subtree has the key greater than the key of x.
That is, if we denote the left subtree of the node x by L(x), its right subtree by R(x) and its key by kx, for each node x we will have
  * if y in L(x) then ky < kx
  * if z in R(x) then kz > kx
The binary search tree is called cartesian if its every node x in addition to the main key kx also has an auxiliary key that we will denote by ax, and for these keys the heap condition is satisfied, that is
  * if y is the parent of x then ay < ax
Thus a cartesian tree is a binary rooted ordered tree, such that each of its nodes has a pair of two keys (k, a) and three conditions described are satisfied.
Given a set of pairs, construct a cartesian tree out of them, or detect that it is not possible.

Input
The first line of the input file contains an integer number N - the number of pairs you should build cartesian tree out of (1 <= N <= 50000). The following N lines contain two integer numbers each - given pairs (ki, ai). For each pair |ki|, |ai| <= 30000. All main keys and all auxiliary keys are different, i.e. ki <> kj and ai <> aj for each i <> j.

Output
On the first line of the output file print YES if it is possible to build a cartesian tree out of given pairs or NO if it is not. If the answer is positive, output the tree itself in the following N lines. Let the nodes be numbered from 1 to N corresponding to pairs they contain as these pairs are given in the input file. For each node output three numbers - its parent, its left child and its right child. If the node has no parent or no corresponding child, output 0 instead.
If there are several possible trees, output any one.

Sample test(s)

Input
7
5 4
2 2
3 9
0 5
1 3
6 6
4 11

Output
YES
2 3 6
0 5 1
1 0 7
5 0 0
2 4 0
1 0 0
3 0 0

Note
Author:	Andrew Stankevich
Resource:	ACM ICPC 2002-2003 NEERC, Northern Subregion
Date:	November, 2002

<|response|>
1. Abridged Problem Statement
You are given N distinct pairs (k_i, a_i). Construct a binary tree of these N nodes satisfying:
  – It is a binary search tree by key k (in-order traversal visits nodes in ascending k).
  – It is a min-heap by auxiliary key a (each parent's a is strictly less than its children's a).
If such a "Cartesian tree" exists (it always does when all keys are distinct), print YES and for each node i (in input order 1…N) output three integers: its parent index, its left-child index, and its right-child index (use 0 if absent).

2. Key Observations
• In any BST with distinct k's, the in-order sequence of nodes must be the nodes sorted by k.
• Once you fix that sequence, the heap-property on a uniquely determines the tree.
• There is a well-known O(N) method using a monotonic stack over the a-values when you process nodes in ascending k. The stack holds the right spine of the tree built so far, with a-values increasing from bottom to top.

3. Full Solution Approach
1. Read the N pairs, remembering each node's original index (1…N).
2. Sort the nodes by k in ascending order.
3. Prepare arrays par[ ], l[ ], r[ ] of size N, initialized to –1 (meaning "none").
4. Maintain an initially empty stack S of node indices (the right spine), with strictly increasing a-values from bottom to top. A "collapse" step pops the top element and, if a previously popped node `last` is being carried, makes `last` the right child of the popped element; it returns the popped index.
5. For each node i in the sorted-by-k order:
   a. Set last = –1.
   b. While S is nonempty and a[S.top] > a[i], call collapse, updating last to the returned popped index.
   c. If last ≠ –1, the chain rooted at `last` becomes the left child of i: par[last] = i, l[i] = last.
   d. Push i onto S.
6. After all nodes are processed, flush the remaining spine with the same collapse routine to wire up the outstanding right-child edges. The unique root is the bottom of S (its parent stays –1).
7. Output "YES", then for i=1…N (in input order) print (par[i]+1, l[i]+1, r[i]+1), converting any –1 to 0.

Time complexity: O(N log N) for sorting + O(N) for the stack algorithm. Memory O(N).

4. C++ Implementation
```cpp
#include <bits/stdc++.h>

using namespace std;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

int n;
vector<pair<int, int>> a;

void read() {
    cin >> n;
    a.resize(n);
    cin >> a;
}

void solve() {
    // Build a Cartesian tree (BST on the main key, min-heap on the auxiliary
    // key) with a monotone stack. We process nodes in increasing main-key
    // order; the stack holds the right spine of the tree built so far, with
    // auxiliary keys increasing from bottom to top. For each new node we pop
    // every spine element whose auxiliary key is larger; the last popped one
    // becomes the new node's left child, and the new node becomes the right
    // child of whatever remains on top. par/l/r store parent, left child and
    // right child (0 meaning none).

    vector<int> order(n);
    iota(order.begin(), order.end(), 0);
    sort(order.begin(), order.end(), [&](int i, int j) {
        return a[i].first < a[j].first;
    });

    vector<int> par(n, -1);
    vector<int> l(n, -1), r(n, -1);
    vector<int> st;

    function<int(int)> collapse = [&](int last) {
        int prev_top = st.back();
        st.pop_back();

        if(last != -1) {
            par[last] = prev_top;
            r[prev_top] = last;
        }

        return prev_top;
    };

    for(int i: order) {
        int last = -1;
        while(!st.empty() && a[st.back()].second > a[i].second) {
            last = collapse(last);
        }

        if(last != -1) {
            par[last] = i;
            l[i] = last;
        }

        st.push_back(i);
    }

    cout << "YES\n";

    int last = -1;
    while(!st.empty()) {
        last = collapse(last);
    }

    for(int i = 0; i < n; i++) {
        cout << par[i] + 1 << ' ' << l[i] + 1 << ' ' << r[i] + 1 << '\n';
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        // cout << "Case #" << test << ": ";
        solve();
    }

    return 0;
}
```

5. Python Implementation with Detailed Comments
```python
import sys
def main():
    data = sys.stdin.read().split()
    it = iter(data)
    N = int(next(it))
    # Read (k, a, original_index)
    nodes = []
    for i in range(N):
        k = int(next(it)); a = int(next(it))
        nodes.append((k, a, i))
    # Sort by k to fix in-order
    nodes.sort(key=lambda x: x[0])

    parent = [-1]*N
    leftC  = [-1]*N
    rightC = [-1]*N

    stack = []  # will store tuples (k, a, idx), but we only need a & idx

    for k, a, idx in nodes:
        last = -1
        # Pop all with larger a
        while stack and stack[-1][1] > a:
            _, _, popped_idx = stack.pop()
            last = popped_idx
        # Attach last popped as left child
        if last != -1:
            parent[last] = idx
            leftC[idx]   = last
        # If anything remains, attach current as right child
        if stack:
            _, _, top_idx = stack[-1]
            parent[idx]     = top_idx
            rightC[top_idx] = idx
        # Push current onto stack
        stack.append((k, a, idx))

    # Print the result
    out = ["YES"]
    for i in range(N):
        p = 0 if parent[i] < 0 else parent[i] + 1
        l = 0 if leftC[i]  < 0 else leftC[i]  + 1
        r = 0 if rightC[i] < 0 else rightC[i] + 1
        out.append(f"{p} {l} {r}")
    sys.stdout.write("\n".join(out))

if __name__ == "__main__":
    main()
```
