As we all know, the way to find the first element on the left that is larger than the current element, is to use the stack.

This problem can be solved in O(n).

But how to find the second element?

Is there a O(n) solution to this?

I use the stack and the priority queue to solve it in O(nlogn), my code is at the bottom:

#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define sz size()
using namespace std;
const int N=1e5+10;
int a[N];
int st[N],ans[N];
struct cmp
{
    bool operator()(pair<int,int>a,pair<int,int>b)
    {
        return a.first>b.first;
    }
};
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    int p=0;
    priority_queue<pair<int,int>,vector<pair<int,int> >,cmp>q;
    for(int i=n;i>=1;i--)
    {
        while(!q.empty()&&q.top().first<a[i])
        {
            ans[q.top().second]=i;// the answer
            q.pop();
        }
        while(p>0&&a[st[p]]<a[i])
        {
            q.push(make_pair(a[st[p]],st[p]));
            p--;
        }
        st[++p]=i;
    }
    while(p>0) ans[st[p]]=0,p--;
    while(!q.empty()) ans[q.top().second]=0,q.pop();
    //there is no answer for these element
    return 0;
}

If anyone has a better solution, please let me know, i'll be very grateful.

———————————————————————————————————————————————————————————————————————————— Hey guys, this problem is over, i find a O(n) solution to solve this problem, just need to use two stack, but to confirm the stack's monotonicity, i need to reverse it.

Here is my final code for this problem:

#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define sz size()
#define pii pair<int,long long>
#define mkp make_pair
using namespace std;
const int N=1e6+10;
stack<int>st1,st2,st3;
int a[N],ans[N];
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=n;i>=1;i--)
    {
        while(!st2.empty()&&a[st2.top()]<a[i])//the second stack
        {
            ans[st2.top()]=i;
            st2.pop();
        }
        while(!st1.empty()&&a[st1.top()]<a[i])
        {
            st3.push(st1.top());//the third stack just use to reverse the element to confirm the monotonicity
            st1.pop();
        }
        st1.push(i);
        while(!st3.empty()) st2.push(st3.top()),st3.pop();//put in the second stack
    }
    while(!st1.empty()) ans[st1.top()]=0,st1.pop();
    while(!st2.empty()) ans[st2.top()]=0,st2.pop();
    for(int i=1;i<=n;i++) cout<<ans[i]<<endl;
    return 0;
}

Sorry to waste your time.