#include "bubblesort2.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
const int MAX_N = 5e5;
const int MAX_AINT = 2 * MAX_N;
const int INF = 1e9;
struct AINT {
struct info {
int minn, maxx;
info operator + ( info x ) {
return { min( minn, x.minn ), max( maxx, x.maxx ) };
}
};
info aint[4 * MAX_AINT];
set<int> poses[MAX_AINT + 1];
void update( int v, int l, int r, int pos, int val ) {
if ( l > pos || r < pos )
return;
if ( l == r ) {
if ( val >= 0 )
poses[l].insert( val );
else
poses[l].erase( -(val - 1) );
aint[v] = (poses[l].empty() ? info{ INF, -INF } : info{ *poses[l].begin(), *poses[l].rbegin() } );
return;
}
int mid = (l + r) / 2;
update( v * 2 + 1, l, mid, pos, val );
update( v * 2 + 2, mid + 1, r, pos, val );
aint[v] = aint[v * 2 + 1] + aint[v * 2 + 2];
}
info query( int v, int l, int r, int lq, int rq ) {
if ( lq > rq )
return { INF, -INF };
if ( l > rq || r < lq )
return { INF, -INF };
if ( lq <= l && r <= rq )
return aint[v];
int mid = (l + r) / 2;
info a = query( v * 2 + 1, l, mid, lq, rq );
info b = query( v * 2 + 2, mid + 1, r, lq, rq );
return a + b;
}
} aint;
struct per {
int i, j;
bool operator < ( const per &x ) const {
return abs( i - j ) > abs( x.i - x.j );
}
};
int leftPair[MAX_N + 1], rightPair[MAX_N + 1];
vector<int> pairs[MAX_N + 1];
map<int, int> mp;
set<per> cand;
vector<int> countScans( vector<int> v, vector<int> pos, vector<int> val ){
int n = v.size();
int q = pos.size();
vector<int> ans( q );
for ( int i = 0; i < n; i++ )
mp[v[i]] = 1;
for ( int i = 0; i < q; i++ )
mp[val[i]] = 1;
int valmax = 0;
for ( auto x: mp )
mp[x.first] = ++valmax;
for ( int i = 0; i < n; i++ )
v[i] = mp[v[i]];
for ( int i = 0; i < q; i++ )
val[i] = mp[val[i]];
for ( int i = 0; i < n; i++ ) {
aint.update( 0, 1, valmax, v[i], i );
int pl = aint.query( 0, 1, valmax, v[i] + 1, valmax ).minn;
leftPair[i] = -1;
if ( 0 <= pl && pl < i ) {
leftPair[i] = pl;
pairs[leftPair[i]].push_back( i );
cand.insert( { leftPair[i], i } );
}
int pr = aint.query( 0, 1, valmax, 1, v[i] - 1 ).maxx;
rightPair[i] = -1;
if ( i < pr && pr < n ) {
rightPair[i] = pr;
pairs[rightPair[i]].push_back( i );
cand.insert( { i, rightPair[i] } );
}
}
for ( int l = 0; l < q; l++ ) {
int i = pos[l];
for ( int j: pairs[i] )
cand.erase( { min( i, j ), max( i, j ) } );
if ( leftPair[i] != -1 )
cand.erase( { leftPair[i], i } );
if ( rightPair[i] != -1 )
cand.erase( { i, rightPair[i] } );
aint.update( 0, 1, valmax, v[i], -(i + 1) );
v[i] = val[l];
aint.update( 0, 1, valmax, v[i], i );
int pl = aint.query( 0, 1, valmax, v[i] + 1, valmax ).minn;
leftPair[i] = -1;
if ( 0 <= pl && pl < i ) {
leftPair[i] = pl;
pairs[leftPair[i]].push_back( i );
cand.insert( { leftPair[i], i } );
}
int pr = aint.query( 0, 1, valmax, 1, v[i] - 1 ).maxx;
rightPair[i] = -1;
if ( i < pr && pr < n ) {
rightPair[i] = pr;
pairs[rightPair[i]].push_back( i );
cand.insert( { i, rightPair[i] } );
}
ans[l] = (cand.empty() ? 0 : cand.begin()->j - cand.begin()->i);
}
return ans;
}
