Code : Speedbreaker

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

bool check(vector<int> &a, int start) {
    int n = a.size();
    vector<int> cnt(n + 1);
    cnt[1] = 1;

    int x = n;
    for (int i = 0; i < start; i++) {
        x = min(x, a[i]);
        cnt[x]++;
        x = max(x - 1, 0);
    }
    x = n;
    for (int i = n - 1; i > start; i--) {
        x = min(x, a[i]);
        cnt[x]++;
        x = max(x - 1, 0);
    }

    int psum = 0;
    for (int i = 0; i <= n; i++) {
        psum += cnt[i];
        if (psum > i) {
            return false;
        }
    }
    return true;
}

void solve(vector<int> &a) {
    int n = a.size();
    int ans = 0;
    for (int start = 0; start < n; start++) {
        if (check(a, start)) {
            ans++;
        }
    }
    cout << ans << "\n";
}

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

    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vector<int> a(n);
        for (int i = 0; i < n; i++) {
            cin >> a[i];
        }
        solve(a);
    }
    return 0;
}

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

void solve(vector<int> &a) {
    int n = a.size();
    int ans = 0;
    vector<int> pmin(n), smin(n);

    int x = n;
    for (int i = 0; i < n; i++) {
        x = min(x, a[i]);
        pmin[i] = x;
        x = max(x - 1, 0);
    }
    x = n;
    for (int i = n - 1; i >= 0; i--) {
        x = min(x, a[i]);
        smin[i] = x;
        x = max(x - 1, 0);
    }

    for (int start = 0; start < n; start++) {
        vector<int> cnt(n + 1);
        cnt[1] = 1;
        bool bad = false;
        for (int i = 0; i < start; i++) {
            cnt[pmin[i]]++;
        }
        for (int i = n - 1; i > start; i--) {
            cnt[smin[i]]++;
        }
        int psum = 0;
        for (int i = 0; i <= n; i++) {
            psum += cnt[i];
            if (psum > i) {
                bad = true;
            }
        }
        ans += !bad;
    }
    cout << ans << "\n";
}

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

    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vector<int> a(n);
        for (int i = 0; i < n; i++) {
            cin >> a[i];
        }
        solve(a);
    }
    return 0;
}

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

void solve(vector<int> &a) {
    int n = a.size();
    int ans = 0;
    vector<int> pmin(n), smin(n);

    int x = n;
    for (int i = 0; i < n; i++) {
        x = min(x, a[i]);
        pmin[i] = x;
        x = max(x - 1, 0);
    }
    x = n;
    for (int i = n - 1; i >= 0; i--) {
        x = min(x, a[i]);
        smin[i] = x;
        x = max(x - 1, 0);
    }

    vector<int> cnt(n + 1);
    cnt[1] = 1;
    for (int i = 0; i < n; i++) {
        cnt[smin[i]]++;
    }

    for (int start = 0; start < n; start++) {
        int old = start - 1;
        if (old >= 0) {
            cnt[pmin[old]]++;
        }
        cnt[smin[start]]--;

        bool bad = false;
        int psum = 0;
        for (int i = 0; i <= n; i++) {
            psum += cnt[i];
            if (psum > i) {
                bad = true;
            }
        }
        ans += !bad;
    }
    cout << ans << "\n";
}

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

    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vector<int> a(n);
        for (int i = 0; i < n; i++) {
            cin >> a[i];
        }
        solve(a);
    }
    return 0;
}

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

void solve(vector<int> &a) {
    int n = a.size();
    int ans = 0;
    vector<int> pmin(n), smin(n);

    int x = n;
    for (int i = 0; i < n; i++) {
        x = min(x, a[i]);
        pmin[i] = x;
        x = max(x - 1, 0);
    }
    x = n;
    for (int i = n - 1; i >= 0; i--) {
        x = min(x, a[i]);
        smin[i] = x;
        x = max(x - 1, 0);
    }

    vector<int> pcnt(n + 1);
    auto add = [&](int idx, int delta) {
        for (int i = idx; i <= n; i++) {
            pcnt[i] += delta;
        }
    };

    vector<int> cnt(n + 1);
    add(1, 1);
    for (int i = 0; i < n; i++) {
        add(smin[i], 1);
    }

    for (int start = 0; start < n; start++) {
        int old = start - 1;
        if (old >= 0) {
            add(pmin[old], 1);
        }
        add(smin[start], -1);

        bool bad = false;
        for (int i = 0; i <= n; i++) {
            if (pcnt[i] > i) {
                bad = true;
            }
        }
        ans += !bad;
    }
    cout << ans << "\n";
}

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

    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vector<int> a(n);
        for (int i = 0; i < n; i++) {
            cin >> a[i];
        }
        solve(a);
    }
    return 0;
}

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

void solve(vector<int> &a) {
    int n = a.size();
    int ans = 0;
    vector<int> pmin(n), smin(n);

    int x = n;
    for (int i = 0; i < n; i++) {
        x = min(x, a[i]);
        pmin[i] = x;
        x = max(x - 1, 0);
    }
    x = n;
    for (int i = n - 1; i >= 0; i--) {
        x = min(x, a[i]);
        smin[i] = x;
        x = max(x - 1, 0);
    }

    vector<int> pcnt(n + 1);
    for (int i = 0; i <= n; i++) {
        pcnt[i] = -i;
    }
    auto add = [&](int idx, int delta) {
        for (int i = idx; i <= n; i++) {
            pcnt[i] += delta;
        }
    };

    add(1, 1);
    for (int i = 0; i < n; i++) {
        add(smin[i], 1);
    }

    for (int start = 0; start < n; start++) {
        int old = start - 1;
        if (old >= 0) {
            add(pmin[old], 1);
        }
        add(smin[start], -1);

        bool bad = false;
        int mx = *max_element(pcnt.begin(), pcnt.end());
        if (mx > 0) {
            bad = true;
        }
        ans += !bad;
    }
    cout << ans << "\n";
}

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

    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vector<int> a(n);
        for (int i = 0; i < n; i++) {
            cin >> a[i];
        }
        solve(a);
    }
    return 0;
}

#include <atcoder/lazysegtree>
#include <bits/stdc++.h>

using namespace std;
using namespace atcoder;

// S is used for querying maximum element
using S = int;

// op is used for querying.
S op(S a, S b) { return max(a, b); }

S e() { return -1e9; }

// F is used for performing range updates.
using F = int;

F composition(F l, F r) { return l + r; }

F id() { return 0; }

// mapping should return f(x). How does S change when you apply the composition
// on it.
// If you add f to an ele, it will change to ele + f
S mapping(F f, S x) { return f + x; }

class LazySegtree {
    int n;
    lazy_segtree<S, op, e, F, mapping, composition, id> *st;

  public:
    LazySegtree(int n) {
        vector<S> initial(n, S{0});
        this->n = n;
        st = new lazy_segtree<S, op, e, F, mapping, composition, id>(initial);
    }

    void add(int l, int r, int delta) {
        if (l > r) {
            return;
        }
        // Atcoder's segtree has [close, open) range.
        st->apply(l, r + 1, delta);
    }

    int query_max(int l, int r) { return st->prod(l, r + 1); }
};

void solve(vector<int> &a) {
    int n = a.size();
    int ans = 0;
    vector<int> pmin(n), smin(n);

    int x = n;
    for (int i = 0; i < n; i++) {
        x = min(x, a[i]);
        pmin[i] = x;
        x = max(x - 1, 0);
    }
    x = n;
    for (int i = n - 1; i >= 0; i--) {
        x = min(x, a[i]);
        smin[i] = x;
        x = max(x - 1, 0);
    }

    LazySegtree st(n + 1);

    vector<int> pcnt(n + 1);
    for (int i = 0; i <= n; i++) {
        st.add(i, i, -i);
    }
    auto add = [&](int idx, int delta) { st.add(idx, n, delta); };

    add(1, 1);
    for (int i = 0; i < n; i++) {
        add(smin[i], 1);
    }

    for (int start = 0; start < n; start++) {
        int old = start - 1;
        if (old >= 0) {
            add(pmin[old], 1);
        }
        add(smin[start], -1);

        bool bad = false;
        int mx = st.query_max(0, n);
        if (mx > 0) {
            bad = true;
        }
        ans += !bad;
    }
    cout << ans << "\n";
}

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

    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vector<int> a(n);
        for (int i = 0; i < n; i++) {
            cin >> a[i];
        }
        solve(a);
    }
    return 0;
}