#include <bits/stdc++.h>
#define inf 1000000001
using namespace std;
struct Seg{
int n;
vector<int> Tree, A;
void init(int N, vector<int> a){
n = N;
Tree.assign(4*n, inf);
for(int i = 0; i < N; i++){
A.push_back(a[i]);
}
build(1, 0, n-1);
}
void build(int node, int l, int r){
if(l == r){
Tree[node] = A[l];
} else {
int mid = (l+r) / 2;
build(2*node, l, mid);
build(2*node+1, mid+1, r);
Tree[node] = min(Tree[2*node], Tree[2*node+1]);
}
}
int min_query(int node, int l, int r, int ql, int qr){
if(qr < l || ql > r ) return inf;
if(ql <= l && r <= qr){
return Tree[node];
}
int mid = (l+r)/2;
return min(min_query(2*node, l, mid, ql, qr), min_query(2*node+1, mid+1, r, ql, qr));
}
void update(int node, int l, int r, int i, int val){
if(l == r) Tree[node] = val, A[i] = val;
else {
int mid = (l+r) / 2;
if(i <= mid){
update(2*node, l, mid, i, val);
} else {
update(2*node+1, mid+1, r, i, val);
}
Tree[node] = min(Tree[2*node], Tree[2*node+1]);
}
}
};
vector<int> count_scans(vector<int> A, vector<int> X, vector<int> V){
int n = A.size();
int m = X.size();
vector<int> answers;
Seg seg;
seg.init(n, A);
for(int q = 0; q < m; q++){
seg.update(1, 0, n-1, X[q], V[q]);
int ans = 0;
for(int i = 0; i < n-1; i++){
int current_number = seg.A[i];
int mi = seg.min_query(1, 0, n-1, i+1, n-1);
if(mi < current_number) ans++;
}
answers.push_back(ans);
}
return answers;
}
/*
int main(){
vector<int> A = {1, 2, 3, 4};
vector<int> X = {0, 2};
vector<int> V = {3, 1};
vector<int> result = count_scans(A, X, V);
for(const int& x : result){
cout << x << ' ';
} cout << endl;
return 0;
}
*/
