#include<bits/stdc++.h>
using namespace std;
const int inf = 1e9;
const int N = (1 << 20);
int cnt[2 * N];
int add[2 * N];
vector<int> maxf(2 * N, -inf);
int lb[2 * N];
int rb[2 * N];
void build(int v = 1, int l = 0, int r = N - 1) {
lb[v] = l;
rb[v] = r;
if(l == r) {
return;
}
int m = (l + r) / 2;
build(2 * v, l, m);
build(2 * v + 1, m + 1, r);
}
void setpush(int v, int x) {
maxf[v] += x;
add[v] += x;
}
void push(int v) {
if(!add[v] || lb[v] == rb[v]) return;
setpush(2 * v, add[v]);
setpush(2 * v + 1, add[v]);
add[v] = 0;
}
void update(int ql, int qr, int x, int v = 1) {
if(rb[v] < ql || lb[v] > qr)
return;
if(ql <= lb[v] && rb[v] <= qr) {
setpush(v, x);
return;
}
push(v);
update(ql, qr, x, 2 * v);
update(ql, qr, x, 2 * v + 1);
cnt[v] = cnt[2 * v] + cnt[2 * v + 1];
maxf[v] = max(maxf[2 * v], maxf[2 * v + 1]);
}
int get_cnt(int ql, int qr, int v = 1) {
if(ql > qr || rb[v] < ql || lb[v] > qr)
return 0;
if(ql <= lb[v] && rb[v] <= qr)
return cnt[v];
push(v);
return get_cnt(ql, qr, 2 * v) + get_cnt(ql, qr, 2 * v + 1);
}
void change(int pos, int x, int y, int v = 1) {
if(rb[v] < pos || lb[v] > pos)
return;
if(lb[v] == rb[v]) {
cnt[v] = x;
maxf[v] = y;
return;
}
push(v);
change(pos, x, y, 2 * v);
change(pos, x, y, 2 * v + 1);
cnt[v] = cnt[v * 2] + cnt[2 * v + 1];
maxf[v] = max(maxf[2 * v], maxf[2 * v + 1]);
}
void insert(int pos, int val) {
change(pos, 1, val - get_cnt(0, pos - 1));
update(pos + 1, N - 1, -1);
}
void erase(int pos) {
change(pos, 0, -inf);
update(pos + 1, N - 1, +1);
}
int find(vector<pair<int, int>> &v, pair<int, int> x) {
int l = -1, r = (int)v.size();
while(r - l > 1) {
int m = (l + r) / 2;
if(v[m] < x) l = m;
else r = m;
}
if(r == (int)v.size() || v[r] != x) return -1;
return r;
}
int n, q;
void compress(vector<int> &a, vector<pair<int, int>> &b) {
int n = (int)a.size();
vector<pair<int, int>> mp;
for(int i = 0; i < n; i++) {
mp.push_back(make_pair(a[i], i));
}
for(auto g : b)
mp.push_back(g);
sort(mp.begin(), mp.end());
int m = (int)mp.size();
int w[m];
int k = 0;
for(int i = 0; i < m; i++) {
if(i && mp[i] != mp[i - 1])
w[i] = ++k;
else w[i] = k;
}
for(int i = 0; i < n; i++) {
a[i] = w[find(mp, make_pair(a[i], i))];
}
for(auto &g : b) {
g.first = w[find(mp, g)];
}
mp.clear();
}
vector<int> countScans(vector<int> a, vector<int> X, vector<int> V) {
build();
n = (int)a.size();
q = (int)X.size();
vector<int> res(q);
vector<pair<int, int>> updates;
for(int i = 0; i < q; i++)
updates.push_back({V[i], X[i]});
compress(a, updates);
for(int i = 0; i < n; i++) {
insert(a[i], i);
}
for(int i = 0; i < q; i++) {
int pos = updates[i].second, val = updates[i].first;
erase(a[pos]);
insert(val, pos);
// if(a[pos] < val) update(a[pos] + 1, val, +1);
// else update(val + 1, a[pos], -1);
a[pos] = val;
res[i] = maxf[1];
}
return res;
}
// int main() {
// ios::sync_with_stdio(0);
// cin.tie(0);cout.tie(0);
// int n, q;
// cin >> n >> q;
// vector<int> A(n);
// vector<int> X(q);
// vector<int> V(q);
// for(int i = 0; i < n; i++) {
// cin >> A[i];
// }
// for(int i = 0; i < q; i++) {
// cin >> X[i] >> V[i];
// }
// vector<int> res = countScans(A, X, V);
// for(int c : res)
// cout << c << '\n';
// }
