#include <bits/stdc++.h>
#include "teams.h"
using namespace std;
typedef long long ll;
const ll D = 1000000000;
struct segTree{
vector<ll> tree[2000002];
void init(int i, int l, int r){
if(l==r){
sort(tree[i].begin(), tree[i].end());
return;
}
int m = (l+r)>>1;
init(i*2, l, m);
init(i*2+1, m+1, r);
tree[i].resize((int)tree[i*2].size() + (int)tree[i*2+1].size());
merge(tree[i*2].begin(), tree[i*2].end(), tree[i*2+1].begin(), tree[i*2+1].end(), tree[i].begin());
}
void addPoint(int i, int l, int r, int x, ll y){
if(l==r){
tree[i].push_back(y);
return;
}
int m = (l+r)>>1;
if(x <= m) addPoint(i*2, l, m, x, y);
else addPoint(i*2+1, m+1, r, x, y);
}
int query(int i, int l, int r, int s, int e, ll vl, ll vr){
if(r<s || e<l) return 0;
if(s<=l && r<=e){
return upper_bound(tree[i].begin(), tree[i].end(), vr) - lower_bound(tree[i].begin(), tree[i].end(), vl);
}
int m = (l+r)>>1;
return query(i*2, l, m, s, e, vl, vr) + query(i*2+1, m+1, r, s, e, vl, vr);
}
pair<int, int> findLim(int i, int l, int r, int x, ll s, ll e, int &lim){
if(l==r){
int tret = upper_bound(tree[i].begin(), tree[i].end(), e) - lower_bound(tree[i].begin(), tree[i].end(), s);
if(tret <= lim){
lim -= tret;
return make_pair(-1, -1);
}
return make_pair(l-1, lim);
}
int m = (l+r)>>1;
if(x>m) return findLim(i*2+1, m+1, r, x, s, e, lim);
if(x <= l){
int tret = upper_bound(tree[i].begin(), tree[i].end(), e) - lower_bound(tree[i].begin(), tree[i].end(), s);
if(tret <= lim){
lim -= tret;
return make_pair(-1, -1);
}
}
auto tmp = findLim(i*2, l, m, x, s, e, lim);
if(tmp.first >= 0) return tmp;
return findLim(i*2+1, m+1, r, x, s, e, lim);
}
} tree;
vector<ll> occ[500002];
int n;
pair<ll, int> p[500002];
void init(int N, int A[], int B[]){
n = N;
for(int i=0; i<n; i++){
p[i] = make_pair(D*A[i] + i, B[i]);
occ[p[i].second].push_back(p[i].first);
tree.addPoint(1, 1, n, p[i].second, p[i].first);
}
tree.init(1, 1, n);
for(int i=1; i<=n; i++) sort(occ[i].begin(), occ[i].end());
}
int k;
int arr[200002];
stack<pair<ll, int> > stk;
int can(int M, int K[]){
k = M;
for(int i=1; i<=k; i++) arr[i] = K[i-1];
sort(arr+1, arr+k+1);
while(!stk.empty()) stk.pop();
stk.push(make_pair(0, n));
for(int i=1; i<=k; i++){
int x = arr[i], lim = arr[i];
while(i<k && arr[i] == arr[i+1]){
i++;
x += arr[i];
if(x>n) return false;
}
while(!stk.empty() && stk.top().second < arr[i]) stk.pop();
while(!stk.empty()){
pair<ll, int> tmp = stk.top();
int ret = tree.query(1, 1, n, lim, tmp.second, tmp.first+1, D*arr[i]+(D-1));
if(ret > x) break;
stk.pop();
x -= ret;
lim = tmp.second+1;
}
if(stk.empty()){
if(x) return false;
stk.push(make_pair(D*arr[i]+(D-1), n));
continue;
}
pair<ll, int> p = stk.top();
pair<int, int> tmp = tree.findLim(1, 1, n, lim, p.first+1, D*arr[i]+(D-1), x);
int bx = tmp.first;
if(x){
auto it = lower_bound(occ[bx+1].begin(), occ[bx+1].end(), p.first+1) + (x-1);
if(stk.top().second == bx+1) stk.pop();
stk.push(make_pair(*it, bx+1));
}
if(stk.top().second == bx) stk.pop();
stk.push(make_pair(D*arr[i]+(D-1), bx));
}
return true;
}
