#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct Segtree{
#define mid ((l + r) >> 1)
struct Node{
int lc, rc, val;
};
int N;
vector<Node> st;
int T;
Segtree() = default;
Segtree(int N) : N(N) {
st.resize(25 * N);
T = 0;
build(0, 1, N);
}
int build(int v, int l, int r){
if (l == r) return v;
st[v].lc = build(++T, l, mid);
st[v].rc = build(++T, mid + 1, r);
return v;
}
int insert(int v, int l, int r, int idx){
int nv = ++T;
if (l == r){
st[nv] = {0, 0, st[v].val + 1};
}
else if (idx <= mid){
st[nv].lc = insert(st[v].lc, l, mid, idx);
st[nv].rc = st[v].rc;
st[nv].val = st[st[nv].lc].val + st[st[nv].rc].val;
}
else{
st[nv].lc = st[v].lc;
st[nv].rc = insert(st[v].rc, mid + 1, r, idx);
st[nv].val = st[st[nv].lc].val + st[st[nv].rc].val;
}
return nv;
}
int insert(int v, int idx){ return insert(v, 1, N, idx); }
int query(int v, int l, int r, int ql, int qr){
if (l > qr || r < ql || ql > qr) return 0;
if (l >= ql && r <= qr) return st[v].val;
return query(st[v].lc, l, mid, ql, qr) +
query(st[v].rc, mid + 1, r, ql, qr);
}
int query(int v, int ql, int qr){ return query(v, 1, N, ql, qr); }
#undef mid
};
Segtree st;
vector<int> rts;
int N;
void init(int N, int A[], int B[]){
::N = N;
st = Segtree(N);
rts.resize(N + 1);
int v = 0;
vector<vector<int>> xs(N + 1);
for (int i = 0; i < N; ++i){
xs[A[i]].push_back(B[i]);
}
for (int i = 1; i <= N; ++i){
rts[i] = rts[i - 1];
for (int y : xs[i]){
v = st.insert(v, y);
rts[i] = v;
}
}
}
int count(int x1, int x2, int y1, int y2){
if (x1 == 0) return st.query(rts[x2], y1, y2);
return st.query(rts[x2], y1, y2) - st.query(rts[x1 - 1], y1, y2);
}
mt19937 gen;
struct Treap{
struct Node{
int p, key, val, tot, sz;
Node *lc, *rc;
Node(int key, int val) : p(gen()), key(key), val(val), tot(val), sz(1), lc(0), rc(0) {}
} *rt = 0;
Treap() : rt(0) {}
int get_sz(Node *v){ return v ? v->sz : 0; }
int get_tot(Node *v){ return v ? v->tot : 0; }
void pull(Node *v){
if (v){
v->tot = v->val + get_tot(v->lc) + get_tot(v->rc);
v->sz = 1 + get_sz(v->lc) + get_sz(v->rc);
}
}
void split(Node *v, Node *&l, Node *&r, int key){
if (!v) return void(l = r = 0);
if (v->key <= key) split(v->rc, v->rc, r, key), l = v;
else split(v->lc, l, v->lc, key), r = v;
pull(l); pull(r);
}
void merge(Node *&v, Node *l, Node *r){
if (!l || !r) return void(v = l ? l : r);
if (l->p > r->p) merge(l->rc, l->rc, r), v = l;
else merge(r->lc, l, r->lc), v = r;
pull(v);
}
void set(int key, int val){
Node *t1, *t2, *t3;
split(rt, t2, t3, key);
split(t2, t1, t2, key - 1);
assert(get_sz(t2));
t2->val = t2->tot = val;
merge(rt, t1, t2);
merge(rt, rt, t3);
}
void insert(int key, int val){
Node *t1, *t2, *t3;
split(rt, t2, t3, key);
split(t2, t1, t2, key - 1);
Node *nd = new Node(key, val);
merge(t1, t1, nd);
merge(t3, t2, t3);
merge(rt, t1, t3);
}
int sum_leq(int key){
Node *t1;
split(rt, t1, rt, key);
int ret = get_tot(t1);
merge(rt, t1, rt);
return ret;
}
void rem_leq(int key){
Node *t1;
split(rt, t1, rt, key);
}
void print(Node *v){
if (v->lc) print(v->lc);
cout << v->key << " ";
if (v->rc) print(v->rc);
}
};
int can(int M, int K[]){
sort(K, K + M);
struct Item{
int y, x, left;
bool operator<(const Item &other) const{
return y < other.y;
}
};
deque<Item> dq;
dq.push_front({N + 1, 0, 0});
Treap t{}; t.rt = 0;
t.insert(N + 1, 0);
// query number of unused points bounded by
// corners (x, y) and (k, y - 1)
// ......
// y**....
// *****.
// *****.
// x k
auto query = [&](int x, int y, int k){
int add = count(0, x, y, y) + count(0, k, 0, y - 1);
auto it = upper_bound(dq.begin(), dq.end(), Item{y, 0, 0});
auto [hy, hx, _] = *it;
int ly = (it == dq.begin() ? 0 : (--it)->y);
int sub = count(0, hx, ly + 1, y) + t.sum_leq(y);
return add - sub;
};
for (int i = 0; i < M; ++i){
// delete corners with y < K[i]
while (dq.front().y < K[i]){
dq.pop_front();
}
t.rem_leq(K[i] - 1);
t.insert(K[i] - 1, count(0, K[i], 0, K[i] - 1));
auto [uy, ux, uleft] = dq.front();
t.set(uy, count(0, ux, K[i], uy) - uleft);
dq.push_front({K[i] - 1, K[i], 0});
// bsearch y
int lo = K[i], hi = N;
while (lo < hi){
int mi = (lo + hi) >> 1;
if (query(K[i], mi, K[i]) >= K[i]) hi = mi;
else lo = mi + 1;
}
int y = lo;
// bsearch x
lo = 1, hi = K[i];
while (lo < hi){
int mi = (lo + hi) >> 1;
if (query(mi, y, K[i]) >= K[i]) hi = mi;
else lo = mi + 1;
}
int x = hi;
int mates = query(x, y, K[i]);
// impossible
if (mates < K[i]){
return 0;
}
// update corners
int hx, hy, hleft;
while (true){
hy = dq.front().y;
hx = dq.front().x;
hleft = dq.front().left;
dq.pop_front();
if (hy > y) break;
}
t.rem_leq(hy);
t.insert(hy, count(0, hx, y + 1, hy) - hleft);
int left = (mates - K[i]);
t.insert(y, count(0, x, y, y) - left);
t.insert(y - 1, count(0, K[i], 0, y - 1));
dq.push_front({hy, hx, hleft});
dq.push_front({y, x, left});
dq.push_front({y - 1, K[i]});
}
return 1;
}
