#include "bubblesort2.h"
#include<bits/stdc++.h>
using namespace std;
template<class T>void maximize(T& a, T b){
if(a < b){
a = b;
}
}
const int lim = 1e6 + 5;
const int INF = 1e9;
int N, bit[lim], st[lim << 2], lazy[lim << 2];
void update(int p, int x){
for(; p <= N; p += p & -p){
bit[p] += x;
}
}
int get(int p){
int ans = 0;
for(; p > 0; p -= p & -p){
ans += bit[p];
}
return ans;
}
void push_down(int id){
st[id << 1] += lazy[id];
lazy[id << 1] += lazy[id];
st[id << 1 | 1] += lazy[id];
lazy[id << 1 | 1] += lazy[id];
lazy[id] = 0;
}
void update_point(int id, int l, int r, int p, int x){
if(l == r){
st[id] = x;
return;
}
push_down(id);
int m = (l + r) >> 1;
if(m < p){
update_point(id << 1 | 1, m + 1, r, p, x);
}
else{
update_point(id << 1, l, m, p, x);
}
st[id] = max(st[id << 1], st[id << 1 | 1]);
}
void update_range(int id, int l, int r, int u, int v, int x){
if(l > v || r < u){
return;
}
if(u <= l && v >= r){
st[id] += x;
lazy[id] += x;
return;
}
push_down(id);
int m = (l + r) >> 1;
update_range(id << 1, l, m, u, v, x);
update_range(id << 1 | 1, m + 1, r, u, v, x);
st[id] = max(st[id << 1], st[id << 1 | 1]);
}
vector<int>countScans(vector<int>a, vector<int>x, vector<int>v){
int n = a.size(), q = x.size();
vector<int>ans(q, 0);
if(n <= 2000 && q <= 2000){
for(int _i = 0; _i < q; _i++){
a[x[_i]] = v[_i];
vector<int>A = a;
while(true){
bool swapped = false;
for(int i = 1; i < n; i++){
if(A[i - 1] > A[i]){
swap(A[i - 1], A[i]);
swapped = true;
}
}
if(!swapped){
break;
}
ans[_i]++;
}
}
}
else if(n <= 8000 && q <= 8000){
vector<int>p(n);
iota(p.begin(), p.end(), 0);
for(int _i = 0; _i < q; _i++){
a[x[_i]] = v[_i];
sort(p.begin(), p.end(), [&] (int i, int j) -> bool{
return a[i] < a[j] || (a[i] == a[j] && i < j);
});
for(int i = 0; i < n; i++){
maximize(ans[_i], p[i] - i);
}
}
}
else if(n <= 50000 && q <= 50000 && *max_element(a.begin(), a.end()) <= 100 && *max_element(v.begin(), v.end()) <= 100){
vector<set<int>>pos(101);
for(int i = 0; i < n; i++){
pos[a[i]].insert(i);
}
for(int _i = 0; _i < q; _i++){
pos[a[x[_i]]].erase(x[_i]);
pos[a[x[_i]] = v[_i]].insert(x[_i]);
for(int i = 1, cnt = 0; i < 101; i++){
if(!pos[i].empty()){
maximize(ans[_i], *pos[i].rbegin() - (cnt += pos[i].size()) + 1);
}
}
}
}
else{
vector<int>compress = a;
for(int& x : v){
compress.emplace_back(x);
}
sort(compress.begin(), compress.end());
compress.resize(unique(compress.begin(), compress.end()) - compress.begin());
vector<set<int>>pos((N = compress.size()) + 1);
memset(bit, 0, sizeof(bit));
for(int i = 0; i < n; i++){
pos[a[i] = lower_bound(compress.begin(), compress.end(), a[i]) - compress.begin() + 1].insert(i);
update(a[i], 1);
}
memset(st, -0x3f, sizeof(st));
memset(lazy, 0, sizeof(lazy));
for(int i = 1, cnt = 0; i <= N; i++){
if(!pos[i].empty()){
update_point(1, 1, N, i, *pos[i].rbegin() - (cnt += pos[i].size()) + 1);
}
}
for(int _i = 0; _i < q; _i++){
if((v[_i] = lower_bound(compress.begin(), compress.end(), v[_i]) - compress.begin() + 1) > a[x[_i]] + 1){
update_range(1, 1, N, a[x[_i]] + 1, v[_i] - 1, 1);
}
else if(v[_i] < a[x[_i]] - 1){
update_range(1, 1, N, v[_i] + 1, a[x[_i]] - 1, -1);
}
pos[a[x[_i]]].erase(x[_i]);
update(a[x[_i]], -1);
update(v[_i], 1);
if(!pos[a[x[_i]]].empty()){
update_point(1, 1, N, a[x[_i]], *pos[a[x[_i]]].rbegin() - get(a[x[_i]]) + 1);
}
else{
update_point(1, 1, N, a[x[_i]], -INF);
}
pos[a[x[_i]] = v[_i]].insert(x[_i]);
update_point(1, 1, N, v[_i], *pos[v[_i]].rbegin() - get(v[_i]) + 1);
ans[_i] = st[1];
}
}
return ans;
}
