CF Div2 1082 C1

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

using ll = long long;

constexpr ll mod = 1e9+7;

void solve(){
    ll n; cin >> n;
    vector<ll> a(n); for (ll &i : a) cin >> i;
    ll ct = 0, mn = -1, mx = -1;
    // mn...mx -> Range of values for each index
    // if out of range -> element cannot be removed
    for (ll i : a){
        // range max reset to i+1
        // if element added to set -> range i+1 to i+1
        if (i >= mn && i <= mx) mx = i+1;
        else ct++, mn = mx = i+1;
    }
    cout << ct << '\n';

    // // ALT APPROACH -> MONOTONIC STACK -> Useful for C2
    // stack<ll> st;
    // for (ll i = n-1; i >= 0; i--){
    //     // our current element is x, it can last accessed element if it is x+1
    //     while (!st.empty() && a[st.top()]-1 == a[i]) st.pop();
    //     st.push(i);
    // }
    // cout << st.size() << '\n';      // element cannot be removed
}

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

    ll t; cin >> t;
    while (t--) solve();
}

// TC -> O(N)
// SC -> O(N)