#include<bits/stdc++.h>
#define fori(i,a,b) for(int i=a;i<=b;i++)
#define pb push_back
using namespace std;
typedef pair<int,int> ii;
typedef tuple<int,int,int> tp;
const int M = 5e5 + 10;
const int SIZE = 500;
int n, q, a[M], uu[M], vv[M];
int f[M];
vector<ii> rrh[SIZE + 10];
int id(int i) {
return (i + SIZE - 1)/SIZE;
}
int get_cnt(int val,int pos)
{
int ret = 0;
int bl = id(pos);
int l = (bl - 1) * SIZE + 1;
for(int i = 1;i <= bl - 1; i++) {
ii tmp = {val,pos};
ret += rrh[i].size() - (upper_bound(rrh[i].begin(), rrh[i].end(), tmp) - rrh[i].begin() );
}
for(int i = l;i <= pos - 1; i++) {
if(a[i] > val) ret++;
}
return ret;
}
int t[SIZE + 10][4 * SIZE + 40],lz[SIZE + 10][4 * SIZE + 40];
void build(int block, int s, int l, int r)
{
if(l == r) {
t[block][s] = f[rrh[block][l].second];
return ;
}
int mid = (l + r)/2;
build(block, s * 2, l, mid);
build(block, s * 2 + 1, mid + 1, r);
t[block][s] = max(t[block][s * 2], t[block][s * 2 + 1]);
}
void lazy(int block,int s)
{
t[block][s * 2] += lz[block][s];
t[block][s * 2 + 1] += lz[block][s];
lz[block][s * 2] += lz[block][s];
lz[block][s * 2 + 1] += lz[block][s];
lz[block][s] = 0;
return ;
}
void upd(int block, int s, int l, int r, int u, int v, int val)
{
if(l > v || r < u) return ;
if(u <= l && r <= v) {
t[block][s] += val;
lz[block][s] += val;
return ;
}
int mid = (l + r)/2;
if(l != r && lz[block][s] != 0) lazy(block,s);
upd(block, s * 2, l, mid, u, v, val);
upd(block, s * 2 + 1, mid + 1, r, u, v, val);
t[block][s] = max(t[block][s * 2], t[block][s * 2 + 1]);
}
void get(int block, int s, int l, int r)
{
if(l == r) {
f[rrh[block][l].second] = t[block][s];
return ;
}
int mid = (l + r)/2;
if(l != r && lz[block][s] != 0) lazy(block,s);
get(block, s * 2, l, mid);
get(block, s * 2 + 1, mid + 1, r);
}
vector<int> countScans(vector<int> A, vector<int> X, vector<int> V)
{
n = A.size();
q = X.size();
vector<int> ans;
cin >> n >> q;
for(int i = 1;i <= n; i++) {
a[i] = A[i - 1];
}
for(int i = 1;i <= q; i++)
{
uu[i] = X[i - 1];
vv[i] = V[i - 1];
uu[i]++;
}
for(int i = 1;i <= n; i++) {
rrh[id(i)].pb({a[i],i});
}
for(int i = 1;i <= id(n); i++) {
sort(rrh[i].begin(), rrh[i].end());
}
// tim f
for(int i = 1;i <= n; i++) f[i] = get_cnt(a[i],i);
for(int i = 1;i <= id(n); i++) {
build(i,1,0,rrh[i].size() - 1);
}
for(int i = 1;i <= q; i++) {
int bl = id(uu[i]);
// upd != block
for(int j = bl + 1; j <= id(n); j++) {
ii tmp = {a[uu[i]],0};
int u = lower_bound(rrh[j].begin(), rrh[j].end(), tmp) - rrh[j].begin() - 1;
int sz = rrh[j].size();
if(u != -1) upd(j, 1, 0, sz - 1, 0, min(u, sz - 1), -1);
tmp = {vv[i], 0};
u = lower_bound(rrh[j].begin(), rrh[j].end(), tmp) - rrh[j].begin() - 1;
//cout << u << " ";
if(u != -1) upd(j, 1, 0, sz - 1, 0, min(u, sz - 1), 1);
}
// upd == block
get(bl,1,0,rrh[bl].size() - 1);
int l = (bl - 1) * SIZE + 1;
int r = min(n,bl * SIZE);
for(int j = uu[i] + 1;j <= r; j++) f[j] = f[j] - (a[j] < a[uu[i]]) + (a[j] < vv[i]);
f[uu[i]] = get_cnt(vv[i], uu[i]);
a[uu[i]] = vv[i];
for(int j = l; j <= r; j++) rrh[bl][j - l] = {a[j],j};
sort(rrh[bl].begin(), rrh[bl].end());
build(bl,1,0,rrh[bl].size() - 1);
// get kq
int kq = 0;
for(int i = 1;i <= id(n); i++) kq = max(kq, t[i][1]);
ans.pb(kq);
}
return ans;
}
