1862C - Flower City Fence - CodeForces Solution

#include<bits/stdc++.h>
using namespace std;

#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define ll long long
#define int long long
#define F first
#define S second






// void dijkstra(int sc){
//     deque<int> q;
//     q.push_front(sc);
//     dist[sc]=0;

//     while(!q.empty()){
//         int cur_node = q.front();
//         q.pop_front();
//         int cur_dist= dist[cur_node];

//         for(auto v : g[cur_node]){
//             if(cur_dist+v.S<dist[v.F]){
//                 dist[v.F]=cur_dist+v.S;
//                 if(v.S==1)q.push_back(v.F);
//                 else q.push_front(v.F);
//             }
//         }
//     }

// }



signed main(){
    IOS
    int t;
    cin>>t;
   
    while(t--){
        int n;
        cin>>n;

        int a[n];

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

        vector<pair<int,int>> ans,cur;

        for(int i=0;i<n;i++){
                if(i==0){
                   // cur.push_back(make_pair(0,a[0]));
                   // ans.push_back(make_pair(a[0],0));
                }
                else{
                    if(a[i]<a[i-1]){
                    cur.push_back(make_pair(i,a[i-1]));
                    ans.push_back(make_pair(a[i-1],i)); 
                    cur.push_back(make_pair(i,a[i]));
                    ans.push_back(make_pair(a[i],i));  
                    }
                    

                }

                if(i==n-1){
                        cur.push_back(make_pair(i+1,a[i]));
                        ans.push_back(make_pair(a[i],i+1));
                        // cur.push_back(make_pair(i+1,0));
                        // ans.push_back(make_pair(0,i+1));
                    }

        //         for(auto v:cur){
        //     cout<<v.F<<v.S<<" ";
        // }
        
        //         for(auto v:ans){
        //     cout<<v.F<<v.S<<" ";
        // }
        
        // cout<<"\n";

        }

        sort(ans.begin(),ans.end());
        sort(cur.begin(),cur.end());
        // for(auto v:ans){
        //     cout<<v.F<<v.S<<" ";
        // }
        // cout<<"\n";
        // for(auto v:cur){
        //     cout<<v.F<<v.S<<" ";
        // }
        // cout<<"\n";
        bool check=true;
        for(int i=0;i<cur.size();i++){
            // cout<<cur[i].F<<ans[i].F<<"\n";

            if(cur[i].F!=ans[i].F||cur[i].S!=ans[i].S){
            check=false;
            // cout<<"hi"<<i<<"\n";
            }
        }
        
        if(check){
        cout<<"YES"<<"\n";
        }    
        else
            cout<<"NO"<<"\n";




}

}