#include <bits/stdc++.h>
using namespace std;
#define sz(x) ((int)(x).size())
const int inf = 1e6;
vector<int> S, L, R;
int upd(int p, int v, int a, int b, int i){
int j = sz(S);
S.push_back(S[i]);
L.push_back(L[i]);
R.push_back(R[i]);
if(a==b) S[j] = v;
else{
int m = (a+b)/2;
if(p <= m){
int k = upd(p, v, a, m, L[i]);
L[j] = k;
}
else{
int k = upd(p, v, m+1, b, R[i]);
R[j] = k;
}
S[j] = S[L[j]]+S[R[j]];
}
return j;
}
int qry(int l, int r, int a, int b, int i){
if(l <= a && b <= r) return S[i];
else if(b < l || r < a) return 0;
int m = (a+b)/2;
return qry(l, r, a, m, L[i]) + qry(l, r, m+1, b, R[i]);
}
int n, cap;
vector<int> ind, roots;
int f(int l, int r, int cnt){ // maximum i s.t. >= cnt intervals starting between l and r contain i
int lo = 0, hi = n+1;
for(int mid = (lo+hi+1)/2; lo<hi; mid=(lo+hi+1)/2){
if(qry(ind[l]+1, ind[r+1], 1, cap, roots[mid]) >= cnt) lo = mid;
else hi = mid-1;
}
return lo;
}
void init(int _n, int* a, int* b){
n = _n;
for(cap = 1; cap <= n+1; cap*=2);
S.resize(2*cap);
L.assign(2*cap, -1);
R.assign(2*cap, -1);
for(int i = cap-1; i > 0; i--) L[i] = 2*i, R[i] = 2*i+1;
ind.resize(n+2);
vector<pair<int, int>> p(n);
for(int i = 0; i < n; i++) p[i] = {a[i], b[i]};
sort(p.begin(), p.end());
int j = 0;
for(int i = 1; i <= n+1; i++){
while(j < n && p[j].first < i) j++;
ind[i] = j;
}
vector<pair<int, int>> q(n);
for(int i = 0; i < n; i++) q[i] = {p[i].second, i};
sort(q.rbegin(), q.rend());
j = 0;
int root = 1;
roots.resize(n+2);
for(int i = n+1; i >= 0; i--){
while(j < n && q[j].first >= i){
root = upd(q[j].second+1, 1, 1, cap, root);
j++;
}
roots[i] = root;
}
// cerr << f(2, 2, 1) << " " << f(1, 2, 1) << " " << f(2, 2, 0) << "\n";
}
int can(int m, int* K){
vector<int> v(m);
for(int i = 0; i < m; i++) v[i] = K[i];
sort(v.begin(), v.end());
// stack<tuple<int, int, int>> st;
// st.emplace(0, 0, inf);
// for(int x : v){
// while(get<2>(st.top()) < x) st.pop();
// auto [dp, y, good] = st.top();
// int cur = dp-x;
// cur += qry(ind[y+1]+1, ind[x+1], 1, cap, roots[x]);
// cerr << good << " " << cur << "\n";
// if(cur < 0) return 0;
// while(!st.empty()){
// tie(dp, y, good) = st.top();
// if(cur < dp) st.pop(), cerr << "pop1\n";
// else{
// int change = f(y, x, cur-dp);
// cerr << change << "\n";
// if(good < change) st.pop(), cerr << "pop2\n";
// else{
// st.emplace(cur, x, change);
// // cerr << y << "\n" << change << "\n";
// break;
// }
// }
// }
// }
vector<int> dp(m+1);
for(int i = 0; i < m; i++){
dp[i+1] = inf;
for(int j = 0; j <= i; j++){
int x = j>0?v[j-1]:0;
int val = dp[j]+qry(ind[x+1]+1, ind[v[i]+1], 1, cap, roots[v[i]])-v[i];
dp[i+1] = min(dp[i+1], val);
}
if(dp[i+1] < 0) return 0;
}
return 1;
}
