#include<bits/stdc++.h>
using namespace std;
#include "bubblesort2.h"
// define
#define execute cerr << " Time: " << fixed << setprecision(6) << (1.0 * clock() / CLOCKS_PER_SEC) << "s\n";
#define ll long long
#define ld double
#define ii pair<int,int>
#define se second
#define fi first
#define iii pair<int,ii>
#define all(v) v.begin(),v.end()
#define bit(x,i) (((x)>>(i))&1LL)
#define flip(x,i) ((x)^(1LL<<(i)))
#define ms(d,x) memset(d,x,sizeof(d))
#define sitingfake 1
#define orz 1
//constant
const ll mod = 1e9 + 7;
const long long linf = 4557430888798830399;
const int inf = 1061109567;
const int maxarr = 1e6 + 5;
const int dx[] = {0,1,-1,0};
const int dy[] = {1,0,0,-1};
template<typename T> bool maximize(T &a, const T &b)
{
if(a < b) {a = b; return 1;}
return 0;
}
template<typename T> bool minimize(T &a, const T &b)
{
if(a > b) {a = b; return 1;}
return 0;
}
inline void Plus(ll & a ,ll b)
{
b %= mod;
a += b;
if(a >= mod) a -= mod;
if(a < 0) a += mod;
return;
}
inline void Mul(ll & a, ll b)
{
a %= mod; b %= mod;
a *= b;
a %= mod;
return;
}
//code
const int maxn = 5e5 + 7;
int a[maxn];
int lazy[8 * maxn] , st[8 * maxn];
int bit[2 * maxn];
int Lim;
int n , q;
void up(int x , int val)
{
for(; x <= Lim; x += (x & -x))
{
bit[x] += val;
}
}
int get(int x)
{
int ans = 0;
for(; x > 0; x -= (x & -x))
{
ans += bit[x];
}
return ans;
}
void Apply(int i ,int val)
{
st[i] += val;
lazy[i] += val;
}
void Push(int i)
{
if(lazy[i])
{
Apply(i * 2 , lazy[i]);
Apply(i * 2 + 1, lazy[i]);
lazy[i] = 0;
}
}
void UpdatePos(int i ,int l,int r, int pos , int val)
{
if(pos >r || pos < l) return;
if(l == r)
{
st[i] = val;
return;
}
int mid = (r + l) >> 1;
Push(i);
UpdatePos(i * 2 , l , mid , pos , val);
UpdatePos(i * 2 + 1, mid + 1 , r , pos , val);
st[i] = max(st[i * 2] , st[i * 2 + 1]);
}
void UpdateRange(int i ,int l ,int r, int u , int v , int val)
{
if(u > r || v < l) return;
if(u <= l && r <= v)
{
st[i] += val;
lazy[i] += val;
return;
}
int mid = (r + l) >> 1;
Push(i);
UpdateRange(i * 2, l , mid , u , v , val);
UpdateRange(i * 2 + 1 , mid + 1 , r , u , v, val);
st[i] = max(st[i * 2] , st[i * 2 + 1]);
}
void Reform(vector <int> &a , vector <int> &x , vector <int> &v)
{
vector <ii> P;
for(int i = 0; i < n ; i++) P.push_back(ii(a[i] , i));
for(int i = 0; i < q ; i++) P.push_back(ii(v[i] , x[i]));
sort(all(P));
P.resize(unique(all(P)) - P.begin());
for(int i = 0; i < n ; i++)
{
a[i] = lower_bound(all(P) , ii(a[i] , i)) - P.begin() + 1;
}
for(int i = 0; i < q ; i++)
{
v[i] = lower_bound(all(P) , ii(v[i] , x[i])) - P.begin() + 1;
}
Lim = P.size();
}
vector <int> countScans(vector <int> a , vector <int> x , vector <int> v)
{
n = a.size();
q = x.size();
vector <int> ans;
Reform(a ,x , v);
for(int i = 0; i < n; i++)
{
up(a[i] , 1);
}
ms(st , -0x3f);
for(int i = 0; i < n; i++)
{
UpdatePos(1 , 1, Lim , a[i] , i - get(a[i] - 1));
}
for(int i = 0; i < q; i++)
{
int Old = a[x[i]] , New = v[i];
if(Old == New)
{
ans.push_back(st[1]);
continue;
}
up(Old , -1);
up(New , 1);
UpdatePos(1 , 1, Lim , Old , -inf);
UpdatePos(1 , 1, Lim , New , x[i] - get(New - 1));
if(Old + 1 < New)
{
UpdateRange(1 , 1 , Lim , Old + 1, New - 1 , 1);// -(-1)
}
else if(New + 1 < Old)
{
UpdateRange(1 , 1, Lim , New + 1, Old - 1 , -1);
}
ans.push_back(st[1]);
a[x[i]] = New;
}
return ans;
}
//void solve(void)
//{
// int n , q;
// cin >> n >> q;
// vector <int> a;
// for(int i = 1; i <= n; i++)
// {
// int x;cin >>x;
// a.push_back(x);
// }
//
// vector <int> x(q) , v(q);
//
// for(int i = 0; i < q; i ++) cin >> x[i] >> v[i];
//
// vector <int> ans = countScans(a , x, v);
// for(int i : ans) cout << i << "\n";
//}
/**
//4 2
//1 2 3 4
//0 3
//2 1
**/
//signed main()
//{
// ios_base::sync_with_stdio(0);
// cin.tie(0);
// cout.tie(0);
//
// #define task ""
//
// if(fopen(task".inp","r"))
// {
// freopen(task".inp","r",stdin);
// freopen(task".out","w",stdout);
// }
//
// int tc; tc = 1;
//
// while(tc--) solve();
//
// //execute;
//}
