#include "king.h"
#include <algorithm>
long long SendInfo(std::vector<int> W, std::vector<int> C) {
int n = W.size();
sort(W.begin(), W.end());
sort(C.begin(), C.end());
long long cansitbegin = -2;
long long cansitend = -2;
int X = n - 1;
for (int i = n - 1; i >= 0; --i) {
int index = lower_bound(C.begin(), C.begin() + X, W[i]) - C.begin();
//int index = mylower_bound(C, X, W[i]);
if (index <= X) {
//printf("값 %d 위치 %d\n", W[i], X);
if (cansitend == -2) {
cansitend = X;
cansitbegin = X;
}
else {
cansitbegin = X;
}
X--;
}
}
if (cansitend == -2) return 1000001LL * 1000002LL;
return cansitend * 1000001LL + cansitbegin;
}
#include "vassal.h"
#include <iostream>
#include <vector>
#include <algorithm>
//using namespace std;
std::vector<int> recover[1000001];
int seg[4000004];
void update(int node, int start, int end, int index, int val) {
if (index<start || index>end) return;
if (start == end) {
seg[node] += val;
return;
}
update(node * 2, start, (start + end) / 2, index, val);
update(node * 2 + 1, (start + end) / 2 + 1, end, index, val);
seg[node] = seg[node * 2] + seg[node * 2 + 1];
}
int sumquery(int node, int start, int end, int i, int j) {
if (start > j || end < i) return 0;
if (i <= start && end <= j) return seg[node];
return sumquery(node * 2, start, (start + end) / 2, i, j) + sumquery(node * 2 + 1, (start + end) / 2 + 1, end, i, j);
}
int kthquery(int node, int start, int end, int kth) {
if (start == end) return start;
if (seg[2 * node] >= kth) {
return kthquery(node * 2, start, (start + end) / 2, kth);
}
else return kthquery(node * 2 + 1, (start + end) / 2 + 1, end, kth - seg[node * 2]);
}
void Init(long long B, std::vector<int> C) {
if (B == 1000001LL * 1000002LL) return;
long long start = B % 1000001LL;
long long endw = B / 1000001LL;
sort(C.begin(), C.end());
//cout << "c의 구간" << '\n';
for (int i = start; i <= endw; ++i) {
update(1, 1, 1000000, C[i], 1);
//cout << C[i] << ' ';
recover[C[i]].push_back(i);
}
//cout << '\n';
}
int Maid(int W) {
//cout <<"N : " << N << '\n';
int before = sumquery(1, 1, 1000000, 1, W - 1);
int cnt = sumquery(1, 1, 1000000, W, 1000000);
//cout << W << ' ';
if (cnt == 0) {
//cout << -1 << '\n';
return -1;
}
else {
int ans = kthquery(1, 1, 1000000, before + 1);
//cout << "C에 해당하는 값 " << ans << ' ';
update(1, 1, 1000000, ans, -1);
int index = recover[ans][recover[ans].size() - 1];
recover[ans].pop_back();
//cout << index << '\n';
return index;
}
}
