1341C - Nastya and Strange Generator - CodeForces Solution

#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define vn vector<ll>v(n)
#define arrn ll arr[n]
#define arrni for(ll i=0;i<n;i++){cin>>arr[i];}
#define vni for(ll i=0;i<n;i++){cin>>v[i];}
#define endl "\n"
#define tc  ll t;cin>>t;while(t--)
#define pb emplace_back
#define mapm map<ll,ll>m
#define sets set<ll>s
#define decsorta sort(arr, arr + n, greater<ll>())
#define decsortv sort(v.begin(),v.end(),greater<ll>())
#define MOD 1000000007
// lower bound --> iterator that points to that index that is just greater or equal to a[i], (if not present then return v.end())
// upper bound --> iterator that points to to that index that is just greater than a[i], (if not present then return v.end())
// auto it = lower_bound(v.begin(),v.end().element);
// get index of lower bound by it-v.begin();
// get value by --> *it
ll fact(ll n){if (n == 0 || n == 1)return 1;return n * fact(n - 1);}
ll nCr(ll n,ll r){return fact(n)/(fact(r)*fact(n-r));}
ll sumofv(vector<ll>&v){ ll sum=0; for(ll i=0;i<v.size();i++){sum+=(v[i]);} return sum;}
ll minelem(vector<ll>&v){ ll min= *min_element(v.begin(),v.end()); return min;}
ll maxelem(vector<ll>&v){ ll max= *max_element(v.begin(),v.end()); return max;}
ll m[100001];

int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
tc{

    ll n;cin>>n;arrn;arrni;
    
    m[0]=0;
    for(ll i=0;i<n;i++)m[arr[i]]=i;
    ll prev=m[1];ll count=1;
    if(n==1)cout<<"Yes"<<endl;
    else{
    ll f=1;ll elem=arr[n-1];
    for(ll i=prev+1;i<n;i++){
        if((arr[i]-arr[i-1])!=1){
            f=0;break;
        }
        count++;
    }
    if(!f)cout<<"No"<<endl;
    else{
        // cout<<prev<<" "<<elem<<endl;
        ll lastel=elem;
        ll f1=1;         
        while(count<n){
            ll pre2=m[elem+1];
            ll ind=m[elem+1];
            // cout<<pre2<<"abc"<<endl;
            for(ll i=ind;i<prev;i++){
                  if(i==ind){count++;lastel=arr[i];
                  elem=arr[i];
                //   cout<<lastel<<endl;
                  }
                  else{
                    if((arr[i]-arr[i-1])!=1){
                        f1=0;break;
                    }
                    else{
                        elem=arr[i];count++;
                        lastel=arr[i];
                    }
                  }
            }
            // cout<<elem<<" "<<pre2<<endl;

            prev=pre2;
            
            if(count==n || lastel==n)break;
            if(!f1){
                cout<<"No"<<endl;
                break;
            }
        }

        if(f1)cout<<"Yes"<<endl;
    }
    }
}



}