#include "teams.h"
#include <bits/stdc++.h>
using namespace std;
const int N=500010, S=1<<19;
int n=0;
vector<int> vec[N];
class PST {
public:
struct Node {
Node *l, *r;
int val;
};
Node *root[N];
void update(int k, int v) {Node *node=update(root[k], 0, S-1, v); root[k]=node;}
int query(int k, int l, int r) {return query(root[k], 0, S-1, l, r);}
int query(int s, int e, int l, int r) {
if(!s) return query(e, l, r);
return query(e, l, r)-query(s-1, l, r);
}
private:
Node* update(Node *prev, int s, int e, int k) {
Node *curr=new Node();
if(prev) curr->l=prev->l, curr->r=prev->r, curr->val=prev->val+1;
else curr->val=1;
if(s==e) return curr;
int m=(s+e)/2;
if(k<=m) curr->l=update(prev?prev->l:NULL, s, m, k);
else curr->r=update(prev?prev->r:NULL, m+1, e, k);
return curr;
}
int query(Node *node, int s, int e, int l, int r) {
if(!node || s>r || l>e) return 0;
if(l<=s && e<=r) return node->val;
int m=(s+e)/2;
return query(node->l, s, m, l, r)+query(node->r, m+1, e, l, r);
}
}T;
void init(int N, int A[], int B[]) {
n=N;
for(int i=0; i<N; i++) vec[A[i]].push_back(B[i]);
for(int i=0; i<N; i++) {
T.root[i]=T.root[i-1];
for(int j:vec[i]) T.update(i, j);
}
}
int can(int M, int K[]) {
vector<int> vec;
vector<array<int, 3>> stk;
stk.push_back({-1, n+1, 0});
for(int i=0; i<M; i++) vec.push_back(K[i]);
sort(vec.begin(), vec.end());
for(int i=0; i<vec.size(); i++) {
int x=vec[i], sum=vec[i], p=i, d=x;
for(int j=i+1; j<vec.size() && vec[i]==vec[j]; j++) p=j, sum+=x;
while(!stk.empty() && stk.back()[1]<x) {
if(stk.back()[1]==x-1) sum+=stk.back()[2];
stk.pop_back();
}
while(!stk.empty()) {
int tmp=T.query(stk.back()[0]+1, x, d, stk.back()[1]);
if(tmp<=sum) sum-=tmp, sum+=stk.back()[2], d=stk.back()[1]+1, stk.pop_back();
else break;
}
if(stk.empty() && sum) return false;
int h=d-1, v=0;
for(int s=d, e=stk.back()[1]; s<=e; ) {
int m=(s+e)/2;
int tmp=T.query(stk.back()[0]+1, x, d, m);
if(tmp<=sum) h=m, v=sum-tmp, s=m+1;
else e=m-1;
}
stk.push_back({x, h, v});
i=p;
}
return true;
}
