#include "teams.h"
#include <bits/stdc++.h>
#define iter(a) a.begin(), a.end()
#define lsort(a) sort(iter(a))
#define gsort(a) sort(iter(a), greater<>())
#define eb emplace_back
#define ef emplace_front
#define pob pop_back()
#define pof pop_front()
#define mp make_pair
#define F first
#define S second
#define uni(a) a.resize(unique(iter(a)) - a.begin())
#define printv(a, b){ \
for(auto pv : a) b << pv << " "; \
b << "\n"; \
}
using namespace std;
typedef long long ll;
typedef long double ld;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
template<typename A, typename B>
ostream& operator<<(ostream& o, pair<A, B> p){
return o << '(' << p.F << ',' << p.S << ')';
}
struct Node{
int v = 0, l = -1, r = -1, tme = 0;
};
vector<Node> st;
vector<int> rt;
int ts = 0;
int n;
int build(int L, int R){
int id = ts++;
if(L == R) return id;
int M = (L + R) / 2;
st[id].l = build(L, M);
st[id].r = build(M + 1, R);
return id;
}
int modify(int x, int L, int R, int oid, int tme){
int id = oid;
if(st[id].tme < tme){
id = ts++;
st[id] = st[oid];
st[id].tme = tme;
}
if(L == R){
st[id].v++;
return id;
}
int M = (L + R) / 2;
if(x <= M) st[id].l = modify(x, L, M, st[id].l, tme);
else st[id].r = modify(x, M + 1, R, st[id].r, tme);
st[id].v = st[st[id].l].v + st[st[id].r].v;
return id;
}
int query(int l, int r, int L, int R, int id){
//cerr << "query " << l << " " << r << " " << L << " " << R << " " << id << "\n";
if(l <= L && R <= r){
//cerr << "OAO\n";
return st[id].v;
}
int M = (L + R) / 2;
if(r <= M) return query(l, r, L, M, st[id].l);
else if(l > M) return query(l, r, M + 1, R, st[id].r);
else return query(l, r, L, M, st[id].l) + query(l, r, M + 1, R, st[id].r);
}
void init(int _n, int A[], int B[]){
n = _n;
st.resize(30 * n);
rt.resize(n + 1);
rt[0] = build(1, n);
vector<vector<int>> pos(n + 1);
for(int i = 0; i < n; i++){
pos[B[i]].eb(A[i]);
}
for(int i = 1; i <= n; i++){
rt[i] = rt[i - 1];
for(int j : pos[i]){
rt[i] = modify(j, 1, n, rt[i], i);
}
}
//cerr << "ok\n";
}
struct seg{
int l, r, cnt = 0, y = 0, up = n;
};
ostream& operator<<(ostream& o, seg s){
return o << '(' << s.l << ',' << s.r << ',' << s.cnt << ',' << s.y << ',' << s.up << ')';
}
int can(int m, int _K[]){
vector<int> K(m);
for(int i = 0; i < m; i++){
K[i] = _K[i];
}
lsort(K);
//cerr << "can " << m << " : ";
//printv(K, cerr);
deque<seg> dq;
for(int i : K){
if(dq.empty()){
dq.eb(seg({1, i, 0, 0, n}));
}
else if(dq.back().r < i){
dq.eb(seg({dq.back().r + 1, i, 0, 0, dq.back().y - 1}));
}
//cerr << "test " << i << "\n";
//printv(dq, cerr);
int cnt = 0;
bool ok = false;
while(!dq.empty()){
//cerr << "owo\n";
seg now = dq.back();
dq.pob;
int l = now.l, r = now.r;
cnt += max(now.cnt, query(l, r, 1, n, rt[i - 1]));
//cerr << "test " << now << " " << cnt << "\n";
int need = cnt + i;
if(query(l, i, 1, n, rt[now.up]) < need) continue;
ok = true;
int lr = 1, rr = now.up;
while(lr < rr){
//cerr << "binary search " << lr << " " << rr << "\n";
int mid = (lr + rr) / 2;
if(query(l, i, 1, n, rt[mid]) >= need) rr = mid;
else lr = mid + 1;
}
dq.eb(seg({l, i, need, lr, now.up}));
break;
}
//cerr << "ok ";
//printv(dq, cerr);
if(!ok) return 0;
}
return 1;
}
