C++ modified monotonic stack + sorting O(n * long(n))
\n\nclass Solution {\npublic:\n    vector<int> secondGreaterElement(vector<int>& nums) {\n        int n = nums.size();\n        vector<int> nextHighest(n, -1);\
```\n\nclass Solution {\npublic:\n    vector<int> secondGreaterElement(vector<int>& nums) {\n        int n = nums.size();\n        vector<int> nextHighest(n, -1);\n        \n        vector<int> high;\n        for(int i=n-1; i>=0; i--){\n            int cur = nums[i];\n            while(high.size() && nums[high.back()]<=nums[i]){\n                high.pop_back();\n            }\n            if(high.size()){\n                nextHighest[i] = high.back();\n            }\n            high.push_back(i);\n        }\n        \n        vector<vector<int>> midVal(n, vector<int>());\n        for(int i=0; i<n; i++){\n            if(nextHighest[i]!=-1){\n                midVal[nextHighest[i]].push_back(i);\n            }\n        }\n        \n        vector<int> ans(n, -1);\n        vector<int> st;\n        \n        for(int i=n-1; i>=0; i--){\n            int cur = nums[i];\n            vector<vector<int>> prev;\n            for(int j=0; j<midVal[i].size(); j++){\n                prev.push_back({nums[midVal[i][j]], midVal[i][j]});\n            }\n            \n            sort(prev.begin(), prev.end());\n            \n            for(auto item:prev){\n                while(st.size() && item[0]>=st.back()){\n                    st.pop_back();\n                }\n                if(st.size()){\n                    ans[item[1]] = st.back();\n                }\n            }\n            while(st.size() && cur>=st.back()){\n                st.pop_back();\n            }\n            \n            st.push_back(nums[i]);\n            \n        }\n        \n        return ans;\n        \n        \n    }\n};\n```
['C']