#include "teams.h"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>
#include <stack>
#include <queue>
typedef long long llong;
const int MAXN = 500000 + 10;
const int INF = 1e9;
int n;
struct MST
{
int a[MAXN];
int b[MAXN];
std::vector <int> tree[4*MAXN];
void build(int l, int r, int node)
{
if (l == r)
{
tree[node].push_back(b[l]);
return;
}
int mid = (l + r) / 2;
build(l, mid, 2*node);
build(mid + 1, r, 2*node + 1);
int lPtr = 0, rPtr = 0;
tree[node].reserve(r - l + 1);
for (int i = l ; i <= r ; ++i)
{
if (lPtr == tree[2*node].size())
{
tree[node].push_back(tree[2*node + 1][rPtr++]);
continue;
}
if (rPtr == tree[2*node + 1].size())
{
tree[node].push_back(tree[2*node][lPtr++]);
continue;
}
if (tree[2*node][lPtr] < tree[2*node + 1][rPtr])
{
tree[node].push_back(tree[2*node][lPtr++]);
} else
{
tree[node].push_back(tree[2*node + 1][rPtr++]);
}
}
}
int binary(int node, int value)
{
int l = -1, r = tree[node].size(), mid;
while (l < r - 1)
{
mid = (l + r) / 2;
if (tree[node][mid] <= value) l = mid;
else r = mid;
}
return r;
}
int query(int l, int r, int node, int queryL, int queryR, int valL, int valR)
{
if (r < queryL || queryR < l)
{
return 0;
}
if (queryL <= l && r <= queryR)
{
return binary(node, valR) - binary(node, valL - 1);
}
int mid = (l + r) / 2;
return query(l, mid, 2*node, queryL, queryR, valL, valR) + query(mid + 1, r, 2*node + 1, queryL, queryR, valL, valR);
}
void build(int _a[], int _b[])
{
for (int i = 1 ; i <= n ; ++i)
{
a[i] = _a[i];
b[i] = _b[i];
}
build(1, n, 1);
}
int query(int l, int r, int valL, int valR)
{
if (l == 0 || r == 0 || valL > valR) return 0;
return query(1, n, 1, l, r, valL, valR);
}
};
int a[MAXN];
int b[MAXN];
int perm[MAXN];
int lastWithA[MAXN];
std::vector <int> v[MAXN];
MST tree;
void init(int N, int A[], int B[])
{
n = N;
std::iota(perm, perm + n, 0);
std::sort(perm, perm + n, [&](int x, int y)
{
return A[x] < A[y] || (A[x] == A[y] && B[x] < B[y]);
});
for (int i = 1 ; i <= n ; ++i)
{
a[i] = A[perm[i - 1]];
b[i] = B[perm[i - 1]];
lastWithA[a[i]] = i;
}
for (int i = 1 ; i <= n ; ++i)
{
lastWithA[i] = std::max(lastWithA[i], lastWithA[i - 1]);
}
// std::cout << "sorted\n";
// for (int i = 1 ; i <= n ; ++i)
// {
// std::cout << a[i] << ' ' << b[i] << '\n';
// }
tree.build(a, b);
}
struct StackElement
{
int l;
int r;
int value;
int left;
};
std::vector <StackElement> st;
int can(int M, int K[])
{
st.clear();
st.push_back({0, 0, INF, 0});
std::sort(K, K + M);
for (int i = 0 ; i < M ; ++i)
{
int want = K[i];
int myValue = K[i];
// std::cout << "i: " << i << ' ' << want << ' ' << lastWithA[K[i]] << '\n';
while (!st.empty())
{
if (st.back().value < myValue)
{
st.pop_back();
continue;
}
int myL = st.back().r + 1;
int myR = lastWithA[K[i]];
// std::cout << "try: " << myL << ' ' << myR << ' ' << myValue << ' ' << n << " = " << tree.query(myL, myR, myValue, n) << " ? " << want << '\n';
if (tree.query(myL, myR, myValue, st.back().value) >= want)
{
int l = myValue - 1, r = n + 1, mid;
while (l < r - 1)
{
mid = (l + r) / 2;
if (tree.query(myL, myR, myValue, mid) < want) l = mid;
else r = mid;
}
st.push_back({myL, myR, r, tree.query(myL, myR, myValue, r) - want});
break;
}
if (st.back().value >= myValue)
{
want += tree.query(st.back().l, st.back().r, myValue, st.back().value) - st.back().left;
}
st.pop_back();
}
// std::cout << "stack after: " << i << '\n';
// for (const StackElement &curr : st)
// {
// std::cout << curr.l << ' ' << curr.r << ' ' << curr.value << ' ' << curr.left << '\n';
// }
if (st.empty())
{
return 0;
}
}
return 1;
}
