1638C - Inversion Graph - CodeForces Solution

#include<bits/stdc++.h>
using namespace std;
 
#define fast                          \
    ios_base::sync_with_stdio(false); \
    cin.tie(0);                       \
    cout.tie(0);
#define int long long
#define pii pair<int,int>
#define ld long double
#define pb push_back
#define all(n) (n).begin(), (n).end()
const ld pie = 3.1415926535897932384626;
void SievePrime(int n)
{  // non-prime -> 0 , prime -> 1
    bool mark[n+1]={0}; // initailly let all are non prime
    mark[2]=1;
    for(int i=3;i<=n;i+=2) // mark all odd no's as prime initially 
    mark[i]=1;
    // thus evens are remains non-prime 
    // 1. optimisation is to iterate over only odd no's (2 and its evens(multiples) are already 0)
    for(int i=3;i<=sqrt(n);i+=2) // skipping even no's
    {   // mark all the multiples of i as non-prime
        for(int j=i*i;j<=n;j+=2*i) // multiples of i before i^2 are already marked and only iterating over multiples if i that are odd no's
        {
            mark[j]=0;
        }
    }
    
    for(int i=2;i<=n;i++)
    {
        if(mark[i]==1)
        cout<<i<<" ";
    }
    cout<<endl;
}
int gcd(int a,int b)
{
 if(b==0)
 return a;
 return gcd(b,a%b);
}
class DSU{
   private :
   vector<int>par,size;
   public :
     DSU(int n){
       par.resize(n+1);
       size.resize(n+1);
       for(int i=0;i<=n;i++){
           par[i]=i;
           size[i]=1;
       }
   }
   public:
   int findpar(int node){
       if(par[node]==node){ // ultimate parent found
         return node;
       }
       return par[node]=findpar(par[node]);
   }
   public:
   void unionBysize(int u,int v){ // we will connect their ultimate parents
       int pu=findpar(u);
       int pv=findpar(v);
       if(pu==pv) return; // already in same component
       if(size[pu]<size[pv]){ // pu is small 
           par[pu]=pv;
           size[pv]+=size[pu];
       }
       else{
           par[pv]=pu;
           size[pu]+=size[pv];
       }
   }
};
pii dfs(int node,vector<vector<int>>&adj,string &s,int &ans){
     pii curr = {0,0};
     for(auto ajn:adj[node]){
         pii res = dfs(ajn,adj,s,ans);
         curr.first+=res.first;
         curr.second+=res.second;
     }
     if(s[node-1]=='W') curr.first+=1;
     else curr.second+=1;
     if(curr.first==curr.second) ans++;
     return curr;
}
void solve()
{
    int n;
    cin>>n;
    vector<int>a(n);
    for(int i=0;i<n;i++) cin>>a[i];
    int mx=INT_MIN;
    int cnt=0;
    for(int i=0;i<n;i++){
         mx=max(mx,a[i]);
         if(mx==i+1)
         cnt++;
    }
    cout<<cnt;
}

int32_t main(){
fast
 int t;
 cin>>t;
 for(int i=1;i<=t;i++)
 {
    solve();
   cout<<'\n';
 }
	return 0;
}