#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 12, inf = 1e8;
int n, m, len, num[maxn * 4], mx[maxn * 4];
vector <int> ans;
vector <pair<int, int>> pos;
map <pair<int, int>, int> cnv;
void update_tree(int l, int r, int u, int k, int L = 0, int R = len){
if(r < L || R < l)
return;
if(l <= L && R <= r){
num[u] += k;
mx[u] += k;
return;
}
int mid = (L + R) / 2;
update_tree(l, r, u * 2, k, L, mid);
update_tree(l, r, u * 2 + 1, k, mid + 1, R);
mx[u] = max(mx[u * 2], mx[u * 2 + 1]) + num[u];
}
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());
len = 1;
for(auto i: pos)
if(cnv[i] == 0){
cnv[i] = len;
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(mx[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 << ' ';
}*/
