#pragma GCC optimize ("Ofast")
//#pragma GCC target ("avx2")
#include "bubblesort2.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 8000, inf = INT_MAX;
int n, suf[N], seg[N*4];
pair<int, int> b[N];
void update(int x, int p=1, int l=0, int r=n-1) {
if (l == r) {
seg[p] = 1;
return;
}
int mid = (l+r) >> 1;
if (x <= mid) update(x, p*2, l, mid);
else update(x, p*2+1, mid+1, r);
seg[p] = seg[p*2] + seg[p*2+1];
}
int query(int L, int R, int p=1, int l=0, int r=n-1) {
if (L <= l && r <= R) {
return seg[p];
}
int mid = (l+r) >> 1;
int x = 0;
if (L <= mid) x += query(L, R, p*2, l, mid);
if (mid+1 <= R) x += query(L, R, p*2+1, mid+1, r);
return x;
}
int solve(vector<int> a) {
memset(seg, 0, sizeof(seg));
for (int i = n-1; i >= 0; i--) {
b[i] = make_pair(a[i], i);
suf[i] = min(a[i], (i+1 < n ? suf[i+1] : inf));
}
sort(b, b+n);
int mx = 0;
for (int i = n-1; i >= 0; i--) {
int idx = b[i].second;
update(b[i].second);
if (idx+1 <= n-1 && suf[idx] < a[idx]) continue;
int x = (idx ? query(0, idx-1) : 0);
mx = max(mx, x);
}
return mx;
}
vector<int> countScans(vector<int> A, vector<int> X, vector<int> V){
n = A.size();
int q = X.size();
vector<int> ans(q);
for (int j = 0; j < q; j++) {
A[X[j]] = V[j];
ans[j] = solve(A);
}
return ans;
}
