#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 12, inf = 1e8;
int n, m, L[maxn * 4], R[maxn * 4], num[maxn * 4], mx[maxn * 4];
vector <int> ans;
vector <pair<int, int>> pos;
struct hash_pair {
template <class T1, class T2>
size_t operator()(const pair<T1, T2>& p) const
{
auto hash1 = hash<T1>{}(p.first);
auto hash2 = hash<T2>{}(p.second);
if (hash1 != hash2) {
return hash1 ^ hash2;
}
// If hash1 == hash2, their XOR is zero.
return hash1;
}
};
unordered_map <pair<int, int>, int, hash_pair> cnv;
void make_tree(int l, int r, int ind){
int mid = (l + r) / 2;
L[ind] = l;
R[ind] = r;
if(l == r)
return;
make_tree(l, mid, ind * 2);
make_tree(mid + 1, r, ind * 2 + 1);
}
void update_tree(int l, int r, int u, int k){
if(r < L[u] || R[u] < l)
return;
if(l <= L[u] && R[u] <= r){
num[u] += k;
mx[u] += k;
return;
}
update_tree(l, r, u * 2, k);
update_tree(l, r, u * 2 + 1, k);
mx[u] = max(mx[u * 2], mx[u * 2 + 1]) + num[u];
}
int get_max(int l, int r, int u){
if(r < L[u] || R[u] < l)
return 0;
if(l <= L[u] && R[u] <= r)
return mx[u];
return max(get_max(l, r, u * 2), get_max(l, r, u * 2 + 1)) + num[u];
}
void set_tree(int l, int k){
int x = get_max(l, l, 1);
update_tree(l, l, 1, k - x);
}
vector <int> countScans(vector <int> a, vector <int> y, vector <int> x){
n = a.size();
m = x.size();
for(int i = 0; i < m; i++)
pos.push_back(make_pair(x[i], y[i]));
for(int i = 0; i < n; i++)
pos.push_back(make_pair(a[i], i));
sort(pos.begin(), pos.end());
int len = 1;
for(auto i: pos)
if(cnv[i] == 0){
cnv[i] = len;
len += 1;
}
make_tree(0, len, 1);
for(int i = 0; i < n; i++){
int now = cnv[make_pair(a[i], i)];
update_tree(now + 1, len, 1, -1);
update_tree(now, now, 1, i);
// cout << now + 1 << ' ' << len << endl;
// cout << now << endl << endl;
}
// cout << get_max(0, len, 1) << endl;
// cout << endl;
for(int i = 0; i < m; i++){
int now = cnv[make_pair(a[y[i]], y[i])];
update_tree(now + 1, len, 1, 1);
update_tree(now, now, 1, -y[i]);
now = cnv[make_pair(x[i], y[i])];
update_tree(now + 1, len, 1, -1);
update_tree(now, now, 1, y[i]);
a[y[i]] = x[i];
ans.push_back(get_max(0, len, 1));
}
return ans;
}
/*
int main(){
vector <int> a, x, y;
int n, m;
cin >> n >> m;
for(int i = 0; i < n; i++){
int b;
cin >> b;
a.push_back(b);
}
for(int i = 0; i < m; i++){
int b, c;
cin >> b >> c;
x.push_back(b);
y.push_back(c);
}
countScans(a, x, y);
for(int i: ans)
cout << i << ' ';
}*/
