Cartesian Tree

Have no idea how to use it. (by ultmaster)

int main() {
    int n;
    int p = 0, rt = 0;
    int now[maxn], h[maxn], lc[maxn], rc[maxn];
    for (int i = 1; i <= n; i++) {
        int last = 0;
        while (p && h[now[p]] >= h[i]) {
            last = now[p];
            now[p--] = 0;
        }
        if (p) rc[now[p]] = i;
        else rt = i;
        lc[i] = last;
        now[++p] = i;
    }
}