Index traversal on Max Segment Tree
Code
# Code
```cpp []
class Solution {
public:
    void update(int node, int start, int end, int pos, int val, vector<int>& c,
                vector<int>& tree) {
        if (start == end) {
            tree[node] = c[pos] = val;
            return;
        }
        int mid = (start + end) >> 1;
        if (start <= pos && pos <= mid)
            update(2 * node + 1, start, mid, pos, val, c, tree);
        else
            update(2 * node + 2, mid + 1, end, pos, val, c, tree);
        tree[node] = max(tree[2 * node + 1], tree[2 * node + 2]);
    }
    int query(int node, int start, int end, int l, int r, vector<int>& tree) {
        if (end < l || start > r)
            return INT_MAX;
        if (tree[node] == 0)
            return INT_MAX;
        if (start == end)
            return start;
        int mid = (start + end) >> 1;
        int ptr = query(2 * node + 1, start, mid, l, r, tree);
        if (ptr != INT_MAX)
            return ptr;
        return query(2 * node + 2, mid + 1, end, l, r, tree);
    }
    vector<int> secondGreaterElement(vector<int>& a) {
        int n = a.size();
        vector<pair<int, int>> b(n);
        for (int i = 0; i < n; i++)
            b[i] = make_pair(a[i], i);
        sort(b.begin(), b.end());
        reverse(b.begin(), b.end());
        vector<int> c(n, 0), tree(4 * n, 0);
        int i = 0, j = 0;
        vector<int> ans(n, -1);
        while (j < n) {
            i = j;
            vector<int> p;
            while (j < n && b[i].first == b[j].first) {
                p.push_back(b[j].second);
                j++;
            }
            for (auto j : p) {
                if (j >= n - 2)
                    continue;
                int r = query(0, 0, n - 1, j + 1, n - 1, tree);
                if (r == INT_MAX)
                    continue;
                r = query(0, 0, n - 1, r + 1, n - 1, tree);
                if (r == INT_MAX)
                    continue;
                ans[j] = a[r];
            }
            for (auto j : p)
                update(0, 0, n - 1, j, 1, c, tree);
        }
        return ans;
    }
};

```
['C++']