1699C - The Third Problem - CodeForces Solution

#include <bits/stdc++.h>
#define int long long
#define M 1000000007
using namespace std;

signed main()
{
    int t;
    cin>>t;

    vector<int> factorial(100005,1);
    for(int i=2;i<100005;i++) factorial[i]=(factorial[i-1]*i)%M;

    while(t--)
    {
        int n;
        cin>>n;

        vector<int> v(n);
        for(int i=0;i<n;i++) cin>>v[i];

        vector<int> fixed(n,0), positionFixed(n,0);
        vector<int> leftReverse(n), right(n);
        
        int mini=n;
        for(int i=0;i<n;i++)
        {
            leftReverse[i]=mini;
            if(v[i]<mini)
            {
                mini=v[i];
                fixed[mini]=1;
                positionFixed[i]=1;
            }
        }
        
        mini=n;
        for(int i=n-1;i>=0;i--)
        {
            right[i]=mini;
            if(v[i]<mini)
            {
                mini=v[i];
                fixed[mini]=1;
                positionFixed[i]=1;
            }
        }
        
        vector<int> left(leftReverse);
        reverse(left.begin(), left.end());

        vector<int> prefixFixed(n);
        prefixFixed[0]=positionFixed[0];
        for(int i=1;i<n;i++) prefixFixed[i]=prefixFixed[i-1]+positionFixed[i];
        
        // for(auto it:positionFixed) cout<<it<<" "; cout<<"\n";
        // for(auto it:prefixFixed) cout<<it<<" "; cout<<"\n";
        // for(auto it:leftReverse) cout<<it<<" "; cout<<"\n";
        // for(auto it:left) cout<<it<<" "; cout<<"\n";
        // for(auto it:right) cout<<it<<" "; cout<<"\n";
        
        int ans=1, extraFixed=0;
        for(int i=2;i<n;i++)
        {
            if(fixed[i]==1) continue;
            
            int l = n - 1 - (upper_bound(left.begin(), left.end(), i) - left.begin() - 1);
            int r = upper_bound(right.begin(), right.end(), i) - right.begin() - 1;
            
            // cout<<l<<" "<<r<<"\n";
            
            if(l<=r)
            {
                int spaces=r-l+1;
                int spacesFixed = ((l==0) ? prefixFixed[r] : prefixFixed[r]-prefixFixed[l-1]) + extraFixed;
                ans = (ans*(spaces-spacesFixed))%M;
            }
            
            extraFixed++;
        }
        
        cout<<ans<<"\n";
    }
}