#include<bits/stdc++.h>
#include "bubblesort2.h"
using namespace std;
#define pii pair<int, int>
const int INF = (1<<30)-1;
struct Tree{
vector<int> tree;
vector<int> d;
int m;
Tree(vector<int> &v){
int m = 1;
while(m<v.size()){
m*=2;
}
m*=2;
tree.resize(m);
d.resize(m);
build(v, 0, v.size()-1, 1);
}
void build(vector<int> &v, int lt, int rt, int t){
if(lt == rt){
tree[t] = v[lt];
d[t] = 0;
}
else{
int mid = (lt+rt)/2;
d[t] = 0;
build(v, lt, mid, t*2);
build(v, mid+1, rt, t*2+1);
tree[t] = min(tree[t*2], tree[t*2+1]) +d[t];
}
}
int update(int l, int r, int v, int lt, int rt, int t){
if(l<=lt && rt<=r){
d[t] += v;
tree[t] += v;
return tree[t];
}
else if(rt<l || r<lt){
return INF;
}
else{
int mid = (lt+rt)/2;
update(l, r, v, lt, mid, t*2);
update(l, r, v, mid+1, rt, t*2+1);
tree[t] = min(tree[t*2], tree[t*2+1]) + d[t];
return tree[t];
}
}
void set_val(int id, int v, int lt, int rt, int t){
if(lt == id && rt == id){
tree[t] = v;
}
else{
int mid =(lt+rt)/2;
if(id<=mid){
set_val(id, v-d[t], lt, mid, t*2);
}
else{
set_val(id, v-d[t], mid+1, rt, t*2+1);
}
tree[t] = min(tree[t*2], tree[t*2+1])+d[t];
}
}
};
struct SumTree{
vector<int> tree;
int m;
SumTree(vector<int> &v){
int m = 1;
while(m<v.size()){
m*=2;
}
m*=2;
tree.resize(m);
build(v, 0, v.size()-1, 1);
}
void build(vector<int> &v, int lt, int rt, int t){
if(lt == rt){
tree[t] = v[lt];
}
else{
int mid = (lt+rt)/2;
build(v, lt, mid, t*2);
build(v, mid+1, rt, t*2+1);
tree[t] = tree[t*2] + tree[t*2+1];
}
//cout<<"buit "<<lt<<" "<<rt<<" "<<tree[t]<<endl;
}
int get_sum(int l, int r, int lt, int rt, int t){
//cout<<"sum "<<lt<<" "<<rt<<" "<<tree[t]<<endl;
if(l<=lt && rt<=r){
return tree[t];
}
else if(rt<l || r<lt || l>r){
return 0;
}
else{
int mid = (lt+rt)/2;
return get_sum(l, r, lt, mid, t*2) + get_sum(l, r, mid+1, rt, t*2+1);
}
}
void add_val(int id, int v, int lt, int rt, int t){
if(lt == id && rt == id){
tree[t] += v;
}
else{
int mid =(lt+rt)/2;
if(id<=mid){
add_val(id, v, lt, mid, t*2);
}
else{
add_val(id, v, mid+1, rt, t*2+1);
}
tree[t] = tree[t*2] + tree[t*2+1];
}
}
};
int n, q;
vector<pii> big;
map<pii, int> small;
vector<int> countScans(vector<int> A,vector<int> X,vector<int> V){
n = A.size();
q=X.size();
for(int i = 0; i<n; i++){
big.push_back(pii(A[i], i));
}
for(int i = 0; i<q; i++){
big.push_back(pii(V[i], X[i]));
}
sort(big.begin(), big.end());
int bs = big.size();
vector<int> v(bs, INF);
for(int i = 0; i<bs; i++){
small[big[i]] = i;
}
vector<pii> target(n);
for(int i = 0; i<n; i++){
target[i] = pii(A[i], i);
}
sort(target.begin(), target.end());
vector<int> oc(bs, 0);
for(int i = 0; i<n; i++){
v[small[target[i]]] = i-target[i].second;
oc[small[target[i]]] =1;
}
/*for(int i = 0; i<bs; i++){
cout<<big[i].first<<" "<<big[i].second<<" "<<v[i]<<" "<<oc[i]<<endl;
}*/
Tree tr = Tree(v);
SumTree s_tr = SumTree(oc);
s_tr.get_sum(0, bs-1, 0, bs-1, 1);
vector<int> r;
for(int i = 0; i<q; i++){
int cur_pos = small[pii(A[X[i]], X[i])];
int pos = small[pii(V[i], X[i])];
//cout<<"from "<<cur_pos<<" to "<<pos<<endl;
A[X[i]] = V[i];
if(cur_pos<pos){
tr.update(cur_pos, pos, -1, 0, bs-1, 1);
}
else{
tr.update(pos, cur_pos, 1, 0, bs-1, 1);
}
s_tr.add_val(cur_pos, -1, 0, bs-1, 1);
s_tr.add_val(pos, 1, 0, bs-1, 1);
int tar = s_tr.get_sum(0, pos-1, 0, bs-1, 1);
//cout<<"new tar "<<tar<<endl;
tr.set_val(cur_pos, INF, 0, bs-1, 1);
tr.set_val(pos, tar-X[i], 0, bs-1, 1);
r.push_back(-tr.tree[1]);
}
return r;
}
