#include "bubblesort2.h"
#include <algorithm>
#include <utility>
#include <vector>
using ll = long long;
ll seg[2000005], lazy[2000005];
inline void paint(int u, ll x)
{
seg[u] += x;
lazy[u] += x;
}
inline void push_down(int u)
{
if (lazy[u])
{
paint(u << 1, lazy[u]);
paint(u << 1 | 1, lazy[u]);
lazy[u] = 0;
}
}
inline void modify(int u, int l, int r, int L, int R, ll x)
{
if (L <= l && r <= R)
{
paint(u, x);
return;
}
push_down(u);
int m = l + r >> 1;
if (L <= m)
modify(u << 1, l, m, L, R, x);
if (m < R)
modify(u << 1 | 1, m + 1, r, L, R, x);
seg[u] = std::max(seg[u << 1], seg[u << 1 | 1]);
}
std::vector<int> countScans(std::vector<int> arr, std::vector<int> qx, std::vector<int> qv)
{
int n = arr.size(), q = qx.size();
std::vector<std::pair<int, int> > app;
for (int i = 0; i < n; i++)
app.emplace_back(arr[i], i);
for (int i = 0; i < q; i++)
app.emplace_back(qv[i], qx[i]);
std::sort(app.begin(), app.end());
app.erase(std::unique(app.begin(), app.end()), app.end());
auto get_idx = [&] (std::pair<int, int> x)
{
return std::lower_bound(app.begin(), app.end(), x) - app.begin();
};
auto update = [&] (int pos, int coef)
{
int idx = get_idx({arr[pos], pos});
modify(1, 0, app.size() - 1, idx, idx, pos * coef);
modify(1, 0, app.size() - 1, get_idx({arr[pos], -1}), app.size() - 1, -coef);
};
for (int i = 0; i < n; i++)
update(i, 1);
std::vector<int> ans(q);
for (int i = 0; i < q; i++)
{
int x = qx[i];
update(x, -1);
arr[x] = qv[i];
update(x, 1);
ans[i] = seg[1] + 1;
}
return ans;
}
