#include <bits/stdc++.h>
#include "bubblesort2.h"
#define rep(a,b,c) for(auto a = (b); a != (c); a++)
#define repD(a,b,c) for(auto a = (b); a != (c); a--)
#define repIn(a, b) for(auto& a : (b))
#define repIn2(a, b, c) for(auto& [a, b] : (c))
#define ll long long
constexpr bool dbg = false;
#define DEBUG if constexpr(dbg)
#define DC DEBUG std::cerr
#define eol std::endl
constexpr ll maxn = 5e5 + 7, treeBase = 1 << 20, inf = 1e18 + 7;
std::map<std::pair<int, int>, int> map;
int n, q;
ll tree[2 * treeBase], lazy[2 * treeBase];
void fixNode(int v) {
// DC << "Fixin " << v << " -> ";
tree[v] = std::max(tree[2 * v] + lazy[2 * v], tree[2 * v + 1] + lazy[2 * v + 1]);
// DC << tree[v] << eol;
}
void add(int l, int r, ll x) {
DC << "add " << l << ' ' << r << ' ' << x << eol;
l += treeBase; r += treeBase;
lazy[l] += x;
if (l != r) lazy[r] += x;
while (l / 2 != r / 2) {
if (l % 2 == 0) lazy[l + 1] += x;
if (r % 2 == 1) lazy[r - 1] += x;
l /= 2; r /= 2;
fixNode(l); fixNode(r);
}
l /= 2;
while (l) fixNode(l), l /= 2;
}
int query() {
DC << "query = " << tree[1] + lazy[1] << eol << eol;
return tree[1] + lazy[1];
}
void mapValues(std::vector<int> &A, std::vector<int> &V, std::vector<int> &X) {
rep(i, 0, n) map[{A[i], i}] = 1;
rep(i, 0, q) map[{V[i], X[i]}] = 1;
int cnt = 0;
repIn2(k, v, map) v = ++cnt;
DEBUG {
DC << "map: " << eol;
repIn2(k, v, map) DC << " {" << k.first << ' ' << k.second << "} => " << v << eol;
}
}
void init(std::vector<int> &A) {
tree[treeBase] = -2 * inf;
repIn2(k, ni, map) {
const auto& [val, index] = k;
add(ni, ni, -inf -(n - index - 1));
}
rep(i, 0, n) {
int mapped = map[{A[i], i}];
int firstSmaller = map.lower_bound({A[i], -1}) -> second - 1;
add(mapped, mapped, inf);
add(0, firstSmaller, 1);
}
}
void makeChange(int &index, int &val, std::vector<int> &A) {
DC << "change " << index << ' ' << val << eol;
int mapped = map[{A[index], index}];
int firstSmaller = map.lower_bound({A[index], -1}) -> second - 1;
add(mapped, mapped, -inf);
add(0, firstSmaller, -1);
A[index] = val;
mapped = map[{A[index], index}];
firstSmaller = map.lower_bound({A[index], -1}) -> second - 1;
add(mapped, mapped, inf);
add(0, firstSmaller, 1);
DC << eol << eol;
}
std::vector<int> countScans(std::vector<int> A,std::vector<int> X,std::vector<int> V) {
n = A.size(), q = X.size();
std::vector<int> ans(q);
mapValues(A, V, X);
init(A);
rep(i, 0, q) makeChange(X[i], V[i], A), ans[i] = query();
return ans;
}
/*
4 2
1 2 3 4
0 3
2 1
*/
