#include "teams.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 5e5+10;
const int B = 2*N;
int n;
struct Node {
int l = 0, r = 0, sum = 0;
Node(int v = 0) { sum = v; }
Node(int _l, int _r);
};
vector<Node> t(1);
Node::Node(int _l, int _r) {
l = _l;
r = _r;
if (l) sum += t[l].sum;
if (r) sum += t[r].sum;
}
int new_node(Node node) {
t.push_back(node);
return t.size()-1;
}
int query(int id, int l, int r, int x, int y) {
if (!id || y <= l || r <= x) return 0;
if (x <= l && r <= y) return t[id].sum;
int m = (l+r)/2;
return query(t[id].l, l, m, x, y)+query(t[id].r, m, r, x, y);
}
int update(int id, int l, int r, int p, int val) {
if (r-l == 1) return new_node(Node(t[id].sum + val));
int m = (l+r)/2;
if (p < m) return new_node(Node(update(t[id].l, l, m, p, val), t[id].r));
else return new_node(Node(t[id].l, update(t[id].r, m, r, p, val)));
}
vector<int> lo(N), hi(N);
vector<vector<int>> y(N);
vector<int> xroot(N, -1);
int rect(int x1, int x2, int y1, int y2) { // (x1, x2] [y1, y2]
return query(xroot[x2], 0, B, y1, y2+1)-query(xroot[x1], 0, B, y1, y2+1);
}
void init(int n, int X[], int Y[]) {
::n = n;
xroot[0] = 0;
for (int i = 0; i < n; i++) y[Y[i]].push_back(i);
int off = 0;
for (int i = 0; i < N; i++) {
lo[i] = i+off, hi[i] = i+off+max((int)y[i].size()-1, 0);
for (int j = 0; j < y[i].size(); j++) Y[y[i][j]] = i+off+j;
off += max((int)y[i].size()-1, 0);
//if (y[i].size()) cout << lo[i] << " " << hi[i] << endl;
}
vector<pair<int, int>> p(n);
for (int i = 0; i < n; i++) p[i] = {X[i], Y[i]};
sort(p.begin(), p.end());
int i = 0;
for (int x = 1; x < N; x++) {
xroot[x] = xroot[x-1];
for (; i < n && p[i].first == x; i++) xroot[x] = update(xroot[x], 0, 2*N, p[i].second, 1);
}
}
int can(int m, int k[]) {
sort(k, k+m);
stack<pair<int, int>> stk;
stk.push({0, B});
for (int i = 0; i < m; i++) {
int x2 = k[i], y1 = lo[k[i]], cnt = 1;
for (; i+1 < m && k[i] == k[i+1]; i++) cnt++;
ll need = k[i]*(ll)cnt;
while (stk.size()) {
auto [cx, cy] = stk.top();
if (cy < y1) {
stk.pop();
continue;
}
int cnt = rect(cx, x2, y1, cy);
//cout << cx << " " << cy << " " << cnt << endl;
if (cnt < need) {
need -= cnt;
stk.pop();
y1 = cy+1;
continue;
}
int l = y1, r = cy, ny = cy;
while (l <= r) {
int mi = (l+r)/2;
int cnt = rect(cx, x2, y1, mi);
if (cnt >= need) {
ny = mi;
r = mi-1;
}
else l = mi+1;
}
need = 0;
y1 = ny;
break;
}
if (need) {
//cout << "Bad" << endl;
return 0;
}
stk.push({x2, y1});
}
//cout << "OK" << endl;
return 1;
}
