// author: khba
#include "bubblesort2.h"
#include "bits/stdc++.h"
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template <typename T>
using ordered_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
#ifdef khba
#include "C:\Users\Asus\Desktop\khba\debug.h"
#else
#define print(...) 42
#endif
struct segtree {
int n;
vector<ordered_multiset<int>> tree;
void init(int n) {
this->n = n;
tree.assign(n << 2, ordered_multiset<int>());
}
segtree(int n) {
this->n = n;
tree.assign(n << 2, ordered_multiset<int>());
}
void update(int idx, int val, bool add = true, int v = 1, int l = 0, int r = -1) {
if (r < 0) r += n;
if (add == false)
tree[v].erase(tree[v].find_by_order(tree[v].order_of_key(val)));
else
tree[v].insert(val);
if (l == r) {
return;
} else {
int m = (l + r) >> 1;
if (idx <= m)
update(idx, val, v << 1, l, m);
else
update(idx, val, v << 1 | 1, m + 1, r);
}
}
int64_t get(int L, int R, int x, bool smaller = false, int v = 1, int l = 0, int r = -1) {
if (r < 0) r += n;
if (L <= l and r <= R)
return smaller ? tree[v].order_of_key(x) : tree[v].size() - tree[v].order_of_key(x + 1);
if (r < L or R < l) return 0;
int m = l + r >> 1;
return get(L, R, x, smaller, v << 1, l, m) + get(L, R, x, smaller, v << 1 | 1, m + 1, r);
}
};
struct Fenwick {
vector<int> f;
Fenwick(int n = 0) : f(n + 1, 0) {}
void add(int i, int v) {
for (++i; i < (int)f.size(); i += i & -i)
f[i] += v;
}
int sum(int i) {
int s = 0;
for (++i; i > 0; i -= i & -i)
s += f[i];
return s;
}
int pref(int i) { return i < 0 ? 0 : sum(i); }
int range(int l, int r) { return pref(r) - pref(l - 1); }
int kth(int k) {
int idx = 0, bit = 1 << 20;
for (; bit; bit >>= 1) {
int nxt = idx | bit;
if (nxt < (int)f.size() && f[nxt] <= k) {
idx = nxt;
k -= f[nxt];
}
}
return idx;
}
};
vector<int> countScans(vector<int> a, vector<int> X, vector<int> V) {
int n = a.size(), q = X.size();
if (n <= 8000) {
segtree sg(n);
vector<int> answer(q);
vector<int> c(begin(a), end(a));
for (int& i : V) c.push_back(i);
sort(begin(c), end(c));
c.erase(unique(begin(c), end(c)), end(c));
for (int& i : a) i = lower_bound(begin(c), end(c), i) - begin(c);
for (int& i : V) i = lower_bound(begin(c), end(c), i) - begin(c);
Fenwick ft(c.size() + 5);
for (int i = 0; i < q; ++i) {
a[X[i]] = V[i];
int ans = 0;
for (int i = 0; i < n; ++i)
ans = max(ans, ft.range(a[i] + 1, c.size())), ft.add(a[i], 1);
for (int i = 0; i < n; ++i) ft.add(a[i], -1);
answer[i] = ans;
}
return answer;
}
ordered_set<int> pos[101];
vector <int> b;
for (int i = 0; i < n; ++i) pos[a[i]].insert(i);
for (int i = 0; i < q; ++i) {
pos[a[X[i]]].erase(pos[a[X[i]]].find_by_order(pos[a[X[i]]].order_of_key(X[i])));
a[X[i]] = V[i];
pos[a[X[i]]].insert(X[i]);
int ans = 0;
for (int x = 0; x <= 100; ++x)
if (pos[x].size()) {
int sum = 0;
for (int y = x + 1; y <= 100; ++y) sum += pos[y].order_of_key(*pos[x].rbegin());
ans = max(ans, sum);
}
b.push_back(ans);
}
return b;
}
