#include "bubblesort2.h"
#include <bits/stdc++.h>
using namespace std;
struct SegTree {
int segLeft, segRight;
vector<int> segTree;
vector<int> lazy;
void init( int l, int r ) {
segLeft = l;
segRight = r;
segTree.resize( 4 * (r - l + 1) );
lazy.resize( 4 * (r - l + 1) );
}
void propag( int v, int l, int r ) {
segTree[v] += lazy[v];
if ( l != r ) {
lazy[v * 2 + 1] += lazy[v];
lazy[v * 2 + 2] += lazy[v];
}
lazy[v] = 0;
}
void update( int v, int l, int r, int lu, int ru, int x ) {
propag( v, l, r );
if ( l > ru || r < lu )
return;
if ( lu <= l && r <= ru ) {
lazy[v] = x;
propag( v, l, r );
return;
}
int mid = (l + r) / 2;
update( v * 2 + 1, l, mid, lu, ru, x );
update( v * 2 + 2, mid + 1, r, lu, ru, x );
segTree[v] = max( segTree[v * 2 + 1], segTree[v * 2 + 2] );
}
void update( int l, int r, int x ) {
update( 0, segLeft, segRight, l, r, x );
}
int query() {
return segTree[0];
}
};
map<long long, int> values;
SegTree inversions;
vector<int> countScans( vector<int> A, vector<int> pos, vector<int> V ){
int n = A.size(), q = V.size();
vector<int> ans( q );
vector<long long> a( n ), val( q );
for ( int i = 0; i < n; i++ )
values[(long long)A[i] * n + i] = 1;
for ( int i = 0; i < q; i++ )
values[(long long)V[i] * n + pos[i]] = 1;
int m = 0;
for ( auto p: values )
values[p.first] = ++m;
for ( int i = 0; i < n; i++ )
a[i] = values[(long long)A[i] * n + i];
for ( int i = 0; i < q; i++ )
val[i] = values[(long long)V[i] * n + pos[i]];
inversions.init( 1, m );
for ( int i = 0; i < n; i++ ) {
inversions.update( a[i], a[i], i );
inversions.update( a[i] + 1, m, -1 );
}
for ( int u = 0; u < q; u++ ) {
int i = pos[u];
inversions.update( a[i], a[i], -i );
inversions.update( a[i] + 1, m, 1 );
a[i] = val[u];
inversions.update( a[i], a[i], i );
inversions.update( a[i] + 1, m, -1 );
ans[u] = inversions.query();
}
return ans;
}
