#include "bubblesort2.h"
#include <bits/stdc++.h>
using namespace std;
template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
//*find_by_order: iterator to kth elem (0-indexed)
//order_of_key: # of items < k (stictly less)
using ll = long long;
const ll mod = 1e9+7;
const int maxn = 1e6 + 5;
const ll inf = 1e18;
struct MaxLazySegmentTree {
vector<ll> t, o;
void init(int n) {
n += 10;
t.resize(4*n);
o.resize(4*n);
}
void push(int v) {
t[2*v]+=o[v];
t[2*v+1]+=o[v];
o[2*v]+=o[v];
o[2*v+1]+=o[v];
o[v]=0;
}
ll queryMax(int v, int tl, int tr, int l, int r) {
if (l>tr||r<tl) return -inf;
if (l<=tl&&tr<=r) {
return t[v];
} else {
push(v);
int tm=(tl+tr)/2;
return max(queryMax(2*v,tl,tm,l,r),queryMax(2*v+1,tm+1,tr,l,r));
}
}
void rangeAdd(int v, int tl, int tr, int l, int r, ll dx) {
if (l>r) return;
if (l>tr||r<tl) return;
if (l<=tl&&tr<=r) {
t[v]+=dx;
o[v]+=dx;
} else {
push(v);
int tm=(tl+tr)/2;
rangeAdd(2*v,tl,tm,l,r,dx);
rangeAdd(2*v+1,tm+1,tr,l,r,dx);
t[v]=max(t[2*v],t[2*v+1]);
}
}
};
template<typename T> struct bit1 {
T add(T x, T y) {
return x+y;
}
int n;
vector<T> t;
void init(int n) {
this->n=n;
t.resize(n+10);
}
T qry(int i) {
assert(i>=1 && i<=n);
T res=0;
for (; i>0; i-=i&-i) res=add(res,t[i]);
return res;
}
void upd(int i, T dx) {
assert(i>=1 && i<=n);
for (; i<=n; i+=i&-i) t[i]=add(t[i],dx);
}
};
bool sorted(vector<int> a) {
int n = a.size();
for (int i=1; i<n; i++) {
if (a[i] < a[i-1]) return false;
}
return true;
}
int brute(vector<int> a) {
int n = a.size();
int res = 0;
while (!sorted(a)) {
res++;
for (int i=0; i<n-1; i++) {
if (a[i] > a[i+1]) swap(a[i], a[i+1]);
}
}
return res;
}
int solve(vector<int> a) {
vector<int> sa = a;
int n = a.size();
sort(sa.begin(), sa.end());
map<int,vector<int>> inds;
for (int i=n-1; i>=0; i--) {
inds[sa[i]].push_back(i);
}
int mx = 0;
for (int i=0; i<n; i++) {
int to = inds[a[i]].back();
if (to < i) {
mx = max(mx, i-to);
}
inds[a[i]].pop_back();
}
return mx;
}
int solveInversion(vector<int> a) {
map<int,int> ind;
ordered_set<pair<int,int>> os;
int hi = 0;
for (int x: a) {
pair<int,int> cur = {x, ind[x]++};
int lte = os.order_of_key(cur);
int inv = int(os.size()) - lte;
hi = max(hi, inv);
os.insert(cur);
}
return hi;
}
void print(vector<int> a) {
for (int i: a) cout<<i<<" ";
cout<<endl;
}
vector<int> solveTask3(vector<int> A, vector<int> X, vector<int> V) {
//cerr<<"task3"<<endl;
int n = A.size();
vector<set<int>> inds(102);
for (int i=0; i<n; i++) {
inds[A[i]].insert(i);
}
vector<int> ans;
for (int q=0; q<(int)X.size(); q++) {
int idx = X[q];
int val = V[q];
inds[A[idx]].erase(idx);
A[idx] = val;
inds[A[idx]].insert(idx);
int mx = 0;
int prev = 0;
for (int i=1; i<=100; i++) {
if (inds[i].empty()) {
continue;
}
int dest = prev + int(inds[i].size()) - 1;
int dist = *inds[i].rbegin() - dest;
mx = max(mx, dist);
prev += int(inds[i].size());
}
//assert(mx == brute(A));
ans.push_back(mx);
}
return ans;
}
vector<int> countScans(vector<int> A, vector<int> X, vector<int> V){
// if (max(*max_element(A.begin(),A.end()), *max_element(V.begin(),V.end())) <= 100) {
// return solveTask3(A,X,V);
// }
int n = A.size();
MaxLazySegmentTree tree; //queryMax, rangeAdd
bit1<ll> bit;
vector<int> ord;
ord.push_back(-1);
ord.push_back(0);
for (auto x: A) ord.push_back(x);
for (auto x: V) ord.push_back(x);
ord.push_back(1000000001);
sort(ord.begin(), ord.end());
ord.erase(unique(ord.begin(), ord.end()), ord.end());
int N = ord.size();
tree.init(N);
bit.init(N);
map<int,set<int>> inds;
for (int i=0; i<n; i++) {
inds[A[i]].insert(i);
int id = lower_bound(ord.begin(), ord.end(), A[i]) - ord.begin();
bit.upd(id, +1);
}
for (auto p: inds) {
int val = p.first;
int rightmost = *p.second.rbegin();
int id = lower_bound(ord.begin(), ord.end(), val) - ord.begin();
tree.rangeAdd(1,1,N,id,id,+rightmost);
int rnk = bit.qry(id-1) + int(p.second.size()) - 1;
tree.rangeAdd(1,1,N,id,id,-rnk);
}
// watch(tree.queryMax(1,1,N,1,N));
// watch(brute(A));
// assert(tree.queryMax(1,1,N,1,N) == brute(A));
// for (int j=1; j<=N; j++) {
// if (inds[ord[j]].empty()) {
// assert(tree.queryMax(1,1,N,j,j)<=0);
// }
// }
// for (int j=1; j<=N; j++) {
// cout<<tree.queryMax(1,1,N,j,j)<<" ";
// }
// cout<<endl;
auto clean = [&](int id) {
ll val = tree.queryMax(1,1,N,id,id);
tree.rangeAdd(1,1,N,id,id,-val);
};
// rightmost - rank
// rank: | <me | + (| =me | - 1)
// auto getRank = [&](int val) {
// assert(inds[val].size());
// int id = lower_bound(ord.begin(), ord.end(), val) - ord.begin();
// return bit.qry(id-1) + int(inds[val].size()) - 1;
// };
int Q = X.size();
vector<int> res(Q);
for (int i=0; i<Q; i++) {
int idx = X[i];
// remove
{
int id = lower_bound(ord.begin(), ord.end(), A[idx]) - ord.begin();
if ((int)inds[A[idx]].size() > 1) tree.rangeAdd(1,1,N,id,id,+1);
tree.rangeAdd(1,1,N,id+1,N,+1);
if (idx == *inds[A[idx]].rbegin()) {
tree.rangeAdd(1,1,N,id,id,-(*inds[A[idx]].rbegin()));
inds[A[idx]].erase(idx);
if (!inds[A[idx]].empty()) {
tree.rangeAdd(1,1,N,id,id,+(*inds[A[idx]].rbegin()));
}
} else {
inds[A[idx]].erase(idx);
}
bit.upd(id,-1);
}
// insert
A[idx] = V[i];
{
int id = lower_bound(ord.begin(), ord.end(), A[idx]) - ord.begin();
bit.upd(id,+1);
tree.rangeAdd(1,1,N,id+1,N,-1);
if (!inds[A[idx]].empty()) {
tree.rangeAdd(1,1,N,id,id,-1);
tree.rangeAdd(1,1,N,id,id,-(*inds[A[idx]].rbegin()));
}
inds[A[idx]].insert(idx);
tree.rangeAdd(1,1,N,id,id,+(*inds[A[idx]].rbegin()));
clean(id);
{
int val = A[idx];
int rightmost = *inds[val].rbegin();
int id = lower_bound(ord.begin(), ord.end(), val) - ord.begin();
tree.rangeAdd(1,1,N,id,id,+rightmost);
int rnk = bit.qry(id-1) + int(inds[val].size()) - 1;
tree.rangeAdd(1,1,N,id,id,-rnk);
}
}
// for (int j=1; j<=N; j++) {
// cout<<tree.queryMax(1,1,N,j,j)<<" ";
// }
// cout<<endl;
res[i] = tree.queryMax(1,1,N,1,N);
//cout<<res[i]<<": expect: "<<brute(A)<<endl;
//assert(res[i] == brute(A));
}
return res;
}
// int main() {
// ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
// int n,q;
// cin>>n>>q;
// vector<int> a(n);
// for (int i=0; i<n; i++) {
// cin>>a[i];
// }
// vector<int> x, v;
// while (q--) {
// int i, val;
// cin>>i>>val;
// x.push_back(i);
// v.push_back(val);
// }
// auto res = countScans(a,x,v);
// for (int i: res) cout<<i<<" ";
// cout<<endl;
// return 0;
// }
