#include "bubblesort2.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define rep(a,b) for(int a = 0; a < (b); ++a)
#define all(t) t.begin(), t.end()
#define pb push_back
const int N = 5e5+5, INF = 2e9+54321;
const ull INF_L = (ll)2e18+54321;
int n,q,base,rozmiar_drzewa;
int B[N], XX[N], YY[N];
vector<int> tree;
void update(int v)
{
v += base, tree[v] += 1, v /= 2;
while(v > 0) tree[v] = tree[v*2] + tree[v*2+1], v /= 2;
}
int query(int l, int p)
{
l = l + base - 1, p = p + base + 1;
int res = 0;
while(l/2 != p/2)
{
if(l % 2 == 0) res += tree[l+1];
if(p % 2 == 1) res += tree[p-1];
l /= 2, p /= 2;
}
return res;
}
vector<int> solve()
{
vector<int> res;
map<int,int> M;
rep(i,n) M[B[i]] = -1;
rep(i,q) M[YY[i]] = -1;
int cnt = -1;
for(auto it = M.begin(); it != M.end(); ++it) it->second = ++cnt;
base = 1;
while(base <= n+q+50) base *= 2;
rozmiar_drzewa = base * 2;
rep(i,n) B[i] = M[B[i]];
rep(z,q)
{
B[XX[z]] = M[YY[z]];
tree.assign(rozmiar_drzewa,0);
int wyn = 0;
rep(i,n)
{
wyn = max(wyn,query(B[i]+1,n+q+3));
update(B[i]);
}
res.pb(wyn);
}
return res;
}
std::vector<int> countScans(std::vector<int> A,std::vector<int> X,std::vector<int> V)
{
n = (int)A.size(), q = (int)X.size();
rep(i,n) B[i] = A[i];
rep(i,q) XX[i] = X[i], YY[i] = V[i];
return solve();
}
