CPP with red-black tree O(n log(n))
Idea:\n\nAt each iteration, for each element on the left side, update the number of elements greater than it.\n\ncpp\nstruct El {\n    int num;\n    mutable int
Idea:\n\nAt each iteration, for each element on the left side, update the number of elements greater than it.\n\n```cpp\nstruct El {\n    int num;\n    mutable int cnt;\n    int idx;\n    \n    bool operator<(const El& rhs) const {\n        if (num == rhs.num) return idx < rhs.idx;\n        return num < rhs.num;\n    }\n};\n\nclass Solution {\npublic:\n    vector<int> secondGreaterElement(vector<int>& nums) {\n        set<El> se; // num, cnt, index\n        int n = nums.size();\n        vector<int> result(n, -1);\n        for (int i = 0; i < n; i++) {\n            auto it = se.upper_bound({nums[i] - 1, 0, 1000000});\n            vector<set<El>::iterator> toErase;\n            for (auto j = se.begin(); j != it; j++) {\n                j->cnt++;\n                if (j->cnt > 1) {\n                    toErase.push_back(j);\n                }\n            }\n            for (auto j: toErase) {\n                result[j->idx] = nums[i];\n                se.erase(j);\n            }\n            \n            se.insert({nums[i], 0, i});\n        }\n        return result;\n    }\n};\n```
[]