The problem can be found here

Observations

I haven’t been doing much compettiive programming and I did not manage to solve the problem myself and the solution does a nice job explaining the solution. Here are just some additonal I thought while reading the editorial.

  1. Looking at cases of length 3 can lead to the observation that $b_0 > b_1 > b_2$ if the array isn’t perfect.
  2. After that, I could’ve tried to generalize this into arrays of greater length. The idea of inversions could’ve come up to figure out a connection between inversions and the problem.
  3. Number of inversions equal the minimum number of swaps to sort the array because you can just bubble sort to reduce the inversions by one and the maximum number of inversions reduced by one swap is 1.
  4. Then, I could’ve figure out that $b_0 > b_1 > b_2$ reduce the number of inversions by 3 and you can’t reduce it by 2 after convincing myself by looking at some more cases.
  5. I now just need to figure out how to found the shortest bounds for every $j$. Finally, for each query I can figure out the rightmost $l$ that contain the bounds for every $r$.

Implementation

Essentially identical to the code in the editorial with some minor differences.

Some comments are added for clarity.

#include <bits/stdc++.h>

using ll = long long;
#define pb push_back

using namespace std;

const int MOD = 1e9+7;
const int MAXN = 2e6+1;
const int INF = 2e9;

void solve() { 
    int n, q;
    cin >> n >> q;

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

    vector<int> l(n+1, 0);
    vector<int> r(n+1, 0);

    for(int i = 1; i <= n; ++i){
        l[i] = i - 1;
        while(l[i] > 0 && v[l[i]] < v[i]){
            l[i] = l[l[i]];
        }
    }

    for(int i = n; i >= 1; --i){
        r[i] = i + 1;
        while(r[i] <= n && v[r[i]] > v[i]){
            r[i] = r[r[i]];
        }
    }

    vector<int> c(n+1, 0);
    
    for(int i = 1; i <= n; ++i){
        if(l[i] == 0 || r[i] == n + 1){continue;}
        c[r[i]] = max(c[r[i]], l[i]);
    }

    for(int i = 1; i <= n; ++i){
        c[i] = max(l[i], l[i-1]);
    }

    while(q--){
        int a, b; cin >> a >> b;
        if(a <= c[b]){
            cout << "NO" << endl;
        }
        else{
            cout << "YES" << endl;
        }
    }
}

int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    // freopen("test.in", "r", stdin);
    // freopen("test.out", "w", stdout);
    int t;
    cin >> t;
    while(t--){
        solve();
    }

    return 0;
}