Source Code
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
#define x           first
#define y           second
#define all(v)      v.begin(),v.end()
#define clr(v,d)    memset(v,d,sizeof(v));

const int N = 1e5 + 10;

const ll mod = 1e9 + 7;

int n , a[N] , fr[N];
pair<int ,int> b[N] ;

int main()
{
    cin.tie(0);
    cin.sync_with_stdio(0);

    int t = 1;
    cin >> t;
   
    while(t--)
    {
        cin >> n;
        int p ;
        for (int i = 0; i < n; ++i) {
            cin >> a[i];
            fr[a[i]] = i ;
            if(!a[i]) p = i ;
        }

        int mx = 1 , l =p  ,r = p;

        b[0] = {p,p};

        ll ans = n;
        if(a[0] == n-1 || a[n-1] == n-1) ans += n-1;

        while(mx < n)
        {
            b[mx] = b[mx-1];
            if(fr[mx] >= b[mx].x && fr[mx] <= b[mx].y)
            {
                mx++;
                continue;
            }
            if(fr[mx] > b[mx].y) b[mx].y = fr[mx] ;
            if(fr[mx] < b[mx].x) b[mx].x = fr[mx] ;
            mx++;
        }

        for (int i = 1; i < n-1 ; ++i) {

            if(b[i] == b[i-1]) continue;

            ll ri = 0, le= 0 ;

            if(a[b[i].x] == i)
            {
                le = b[i-1].x - b[i].x ;

                if(fr[i+1] > b[i].y )
                {
                    ri = fr[i+1] - b[i].y;
                }
                else
                {
                    ri = n - b[i].y ;
                }
            }
            else
            {
                ri = b[i].y - b[i-1].y ;

                if(fr[i+1] < b[i].x )
                {
                    le = b[i].x - fr[i+1];
                }
                else
                {
                    le = b[i].x+1 ;
                }
            }

            ans += ri*le*i ;

            //cout << i << " " << le << " " << ri << "\n" ;
        }
        cout << ans << "\n" ;
    }

    return 0;
}
Copy
Mex MuhammadHassan
GNU G++17
9 ms
364 KB
Wrong Answer