#include "king.h"
#include<map>
#include<vector>
#include<algorithm>
#include<iostream>
#define ll long long
#define rep(i,a,b) for(int i = a;i < b;i++)
#define MAXN 300003
long long SendInfo(std::vector<int> W, std::vector<int> C) {
int n = W.size();
int cur = 0;
sort(W.rbegin(),W.rend());
sort(C.rbegin(),C.rend());
rep(i,0,n)
{
if(W[i] <= C[cur])
{
cur++;
}
}
return W[n-cur];
}
#include "vassal.h"
#include<map>
#include<vector>
#include<iostream>
#include<algorithm>
#include<set>
#define ll long long
#define pi pair < ll,ll >
#define mp(a,b) make_pair(a,b)
#define rep(i,a,b) for(int i = a;i < b;i++)
#define MAXN 1000003
#define INF 1e17
using namespace std;
long long maxi;
ll seg[4*MAXN];
vector < vector < ll > > chairs(MAXN);
ll sz = MAXN-2;
void update(ll low,ll high,ll pos,ll slow,ll val)
{
if(low == high && low == slow)
{
seg[pos] += val;
return;
}
if(low > slow || high < slow)
return;
ll mid = (low+high)/2;
update(low,mid,pos*2+1,slow,val);
update(mid+1,high,pos*2+2,slow,val);
seg[pos] = seg[pos*2+1]+seg[pos*2+2];
return;
}
ll query(ll low,ll high,ll pos,ll slow)
{
ll mid= (low+high)/2;
if(low >= slow)
{
if(seg[pos] == 0)
return -1;
else if(low == high)
return low;
else if(seg[pos*2+1] > 0)
return query(low,mid,pos*2+1,slow);
else
return query(mid+1,high,pos*2+2,slow);
}
if(high < slow)
return -1;
return max(query(low,mid,pos*2+1,slow),query(mid+1,high,pos*2+2,slow));
}
void Init(long long B, std::vector<int> C)
{
int n = C.size();
maxi = B;
rep(i,0,n)
{
update(0,sz,0,C[i],1);
chairs[C[i]].push_back(i);
}
return;
}
int Maid(int W){
if(W>maxi)
return -1;
else
{
ll cur = query(0,sz,0,W);
if(cur == -1)
return -1;
else
{
update(0,sz,0,cur,-1);
ll ch = chairs[cur][0];
chairs[cur].erase(chairs[cur].begin());
return ch;
}
}
}
