#include "bubblesort2.h"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>
#include <stack>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template <typename T>
using OSet = tree <T, null_type, std::less <T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long llong;
const int MAXN = 500000 + 10;
const int INF = 1e9;
int n, q;
int in[MAXN];
int order[MAXN];
llong a[MAXN];
std::vector <int> countScans(std::vector <int> A, std::vector <int> X, std::vector <int> V)
{
n = A.size();
q = X.size();
for (int i = 1 ; i <= n ; ++i)
{
a[i] = A[i - 1];
}
std::vector <int> answer(q, 0);
for (int query = 0 ; query < q ; ++query)
{
OSet <llong> s;
a[X[query] + 1] = V[query];
for (int i = 1 ; i <= n ; ++i)
{
answer[query] = std::max(answer[query], (int)s.size() - (int)s.order_of_key(n * a[i] + i));
s.insert(n * a[i] + i);
}
}
return answer;
}
