#include <bits/stdc++.h>
#include "bubblesort2.h"
#define sz(x) (int)(x.size() )
#define all(x) x.begin(),x.end()
const int MAX = 1e6+10 ;
const int inf = 1e8+10 ;
using namespace std ;
int Key ;
struct Tree
{
int tree[MAX*4] ;
int lz[MAX*4] ;
int m(int l, int r ) { return (l+r)>>1 ; }
void refresh(int pos, int l, int r )
{
tree[pos] += lz[pos] ;
if( l == r ) return (void)(lz[pos] = 0 ) ;
lz[pos<<1] += lz[pos] ;
lz[pos<<1|1] += lz[pos] ;
lz[pos] = 0 ;
}
void updInterval(int pos, int l,int r, int beg, int en, int val )
{
refresh(pos,l,r) ;
if( l > en || r < beg ) return ;
if( l >= beg && r <= en )
{
lz[pos] += val ;
refresh(pos,l,r) ;
return ;
}
updInterval(pos<<1 , l, m(l,r) , beg, en, val ) ;
updInterval(pos<<1|1 , m(l,r)+1, r, beg, en, val ) ;
tree[pos] = max(tree[pos<<1], tree[pos<<1|1] ) ;
}
void updPoint(int pos, int l ,int r, int idx, int val )
{
refresh(pos,l,r) ;
if( l > idx || r < idx ) return ;
if( l == r ) return (void)(tree[pos] = val) ;
updPoint(pos<<1 , l ,m(l,r), idx, val ) ;
updPoint(pos<<1|1 , m(l,r)+1, r, idx, val ) ;
tree[pos] = max(tree[pos<<1] , tree[pos<<1|1] ) ;
}
int getMax() { refresh(1,0,1) ; return tree[1] ; }
} seg ;
struct Bit
{
int bit[MAX] ;
void upd(int pos, int x ) { for(; pos < MAX ; pos += pos & -pos ) bit[pos] += x ; }
int qry(int pos )
{
int tot = 0 ;
for(; pos > 0 ; pos -= pos & -pos ) tot += bit[pos] ;
return tot ;
}
} bit ;
vector<int> countScans( vector<int> A, vector<int> X, vector<int> V)
{
int n = sz(A) ;
int q = sz(V) ;
map< pair<int,int> , int > compression ;
for(int i = 0 ; i < n ; i++ ) compression[ make_pair(A[i],i) ] = 0 ;
for(int i = 0 ; i < q ; i++ ) compression[ make_pair(V[i], X[i]) ] = 0 ;
for(auto &e : compression ) e.second = ++Key ;
for(int i = 0 ; i < n ; i++ ) A[i] = compression[ make_pair(A[i], i) ] ;
for(int i = 0 ; i < q ; i++ ) V[i] = compression[ make_pair(V[i] , X[i] ) ] ;
seg.updInterval(1,1,Key, 1,Key, -inf ) ;
for(int i = 0 ; i < n ; i++ ) bit.upd(A[i], 1) ;
for(int i = 0 ; i < n ; i++ ) seg.updPoint(1,1, Key,A[i], i-bit.qry(A[i]-1) ) ;
vector<int> ans ;
for(int i = 0 ; i < q ; i++ )
{
bit.upd( A[ X[i] ] , -1 ) ;
bit.upd( V[i] , 1 ) ;
seg.updInterval( 1 , 1 , Key , A[ X[i] ] + 1 , Key , 1 ) ;
seg.updInterval(1 , 1 , Key , V[i] + 1 , Key , -1 ) ;
seg.updPoint(1 , 1 , Key , A[ X[i] ] , -inf ) ;
seg.updPoint(1,1,Key, V[i] , X[i] - bit.qry(V[i] - 1) ) ;
A[X[i]] = V[i] ;
ans.push_back( seg.getMax() ) ;
}
return ans ;
}
