#include "bubblesort2.h"
#include <set>
#include <algorithm>
using namespace std;
static int stupid(vector<int> A)
{
int res = 0;
int n = A.size();
while (true)
{
bool was = false;
for (int i = 1; i < n; ++i)
{
if (A[i-1] > A[i])
{
swap(A[i-1], A[i]);
was = true;
}
}
if (was)
++res;
else
break;
}
return res;
}
static int get(vector<int> &f, int x)
{
int res = 0;
for (; x >= 0; x = (x&(x+1))-1)
res += f[x];
return res;
}
static void add(vector<int> &f, int x, int v)
{
for (; x < f.size(); x |= (x+1))
f[x] += v;
}
static int stupid1(vector<int> A)
{
int n = A.size();
int res = 0;
for (int i = 1; i < n; ++i)
{
int c = 0;
for (int j = 0; j < i; ++j)
if (A[i] < A[j])
++c;
res = max(res, c);
}
return res;
}
static int smart(const vector<int> &A, vector<int> &F, const vector<int> &all)
{
int n = A.size();
int res = 0;
for (int i = 0; i < n; ++i)
{
res = max(res, i - get(F, A[i]));
add(F, A[i], 1);
}
for (int i = 0; i < n; ++i)
add(F, A[i], -1);
return res;
}
static int smart1(const vector<int> &A)
{
int n = A.size();
int res = 0;
int p = int(2e9);
for (int i = n - 1; i > 0; --i)
{
if (A[i] < p)
{
p = A[i];
int c = 0;
for (int j = 0; j < i; ++j)
if (A[i] < A[j])
++c;
res = max(res, c);
}
}
return res;
}
vector<int> countScans(vector<int> A, vector<int> X, vector<int> V)
{
int Q = X.size();
int N = A.size();
vector<int> answer(Q);
for (int j = 0; j < Q; ++j)
{
A[X[j]] = V[j];
answer[j] = smart1(A);
}
return answer;
vector<int> all(N + Q);
for (int i = 0; i < N; ++i)
all[i] = A[i];
for (int i = 0; i < Q; ++i)
all[N+i] = V[i];
sort(all.begin(), all.end());
vector<int>::iterator z = unique(all.begin(), all.end());
all.resize(z - all.begin());
/*for (int j = 0; j < all.size(); ++j)
printf("%d ", all[j]);
printf("\n");*/
if (all.back() <= 100)
{
vector<int> T[101];
for (int x = 0; x <= 100; ++x)
T[x].resize(2*N);
for (int j = 0; j < N; ++j)
for (int x = A[j] - 1; x >= 0; --x)
add(T[x], j, 1);
set<int> pos[101];
for (int j = 0; j < N; ++j)
pos[A[j]].insert(-j);
for (int j = 0; j < Q; j++)
{
int p = X[j];
for (int x = A[p] - 1; x >= 0; --x)
{
add(T[x], p, -1);
}
pos[A[p]].erase(-p);
A[p] = V[j];
for (int x = V[j] - 1; x >= 0; --x)
add(T[x], p, 1);
pos[V[j]].insert(-p);
int ans = 0;
for (int x = 0; x <= 100; ++x)
if (pos[x].size())
{
ans = max(ans, get(T[x], -*(pos[x].begin())));
}
answer[j] = ans;
}
}
else
{
for (int j = 0; j < N; j++)
A[j] = lower_bound(all.begin(), all.end(), A[j]) - all.begin();
for (int j = 0; j < Q; j++)
V[j] = lower_bound(all.begin(), all.end(), V[j]) - all.begin();vector<int> F(all.size());
for (int j = 0; j < Q; j++)
{
A[X[j]] = V[j];
answer[j] = smart(A, F, all);
}
}
return answer;
}
