#include "bubblesort2.h"
#include <algorithm>
#include <utility>
using ll = long long;
namespace segT
{
ll seg[4000005], lazy[4000005];
inline void paint(int u, int 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, int 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> qy)
{
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(qy[i], qx[i]);
std::sort(app.begin(), app.end());
app.erase(std::unique(app.begin(), app.end()), app.end());
auto search = [&] (int pos, int val)
{
return std::lower_bound(app.begin(), app.end(), std::make_pair(pos, val)) - app.begin();
};
auto modify = [&] (int pos, int coef)
{
int idx = search(arr[pos], pos);
segT::modify(1, 0, app.size() - 1, idx, idx, pos * coef);
segT::modify(1, 0, app.size() - 1, search(arr[pos], -1), app.size() - 1, -coef);
};
for (int i = 0; i < n; i++)
modify(i, 1);
std::vector<int> ans(q);
for (int i = 0; i < q; i++)
{
int p = qx[i];
modify(p, -1);
arr[p] = qy[i];
modify(p, 1);
ans[i] = segT::seg[1] + 1;
}
return ans;
}
