vector<int> secondlargest(vector<int> &a)
{
    int n = a.size();
    vector<int> idx(n+1);
    int pos = -1;
    vector<vector<int>> search(n+1);
    vector<int> cursearch(n+1);
    vector<int> answer(n);
    for (int i = 0; i<n; i++)
    {
        while (pos>=0&&a[idx[pos]]<=a[i])
        {
            search[i].push_back(idx[pos]);
            pos--;
        }
        idx[pos+1] = i;
        if (pos==-1) {answer[i] = -1; pos = 0; continue;}
        int c = idx[pos];
        while (cursearch[c]<search[c].size()&&a[search[c][cursearch[c]]]<=a[i]) cursearch[c]++;
        if (cursearch[c]==search[c].size())
        {
            if (pos>0) answer[i] = idx[pos-1];
            else answer[i] = -1;
            pos++;
        }
        else {answer[i] = search[c][cursearch[c]]; pos++;}
    }
    return answer;
}