#include "teams.h"
#include<bits/stdc++.h>
using namespace std;
const int maxn = 5e5+5;
const long long INF = 1e18;
const int blsz = 100;
vector<int> FW[maxn];
vector<int> d[maxn];
int pfx_all[maxn], sfx_all[maxn];
int L[maxn], R[maxn];
int dp[maxn];
vector<int> precalc[maxn];
vector<int> pos[maxn];
map<pair<int, int>, int> mp;
int n;
struct node{
node *lc, *rc;
int sum;
node(int _sum = 0): sum(_sum), lc(nullptr), rc(nullptr){};
void build(int l = 1, int r = n){
if(l == r)return;
lc = new node();
rc = new node();
int mid = (l+r)>>1;
lc->build(l, mid);
rc->build(mid+1, r);
}
void upd(node &old_tree, int pos, int l = 1, int r = n){
sum = old_tree.sum + 1;
if(l == r)return;
int mid = (l+r)>>1;
if(pos <= mid){
rc = old_tree.rc;
lc = new node();
lc->upd(*old_tree.lc, pos, l, mid);
}
else {
lc = old_tree.lc;
rc = new node();
rc->upd(*old_tree.rc, pos, mid+1, r);
}
}
int query(int pos, int l = 1, int r = n){
if(l == r)return sum;
int mid = (l+r)>>1;
if(pos <= mid)return lc->query(pos, l, mid);
else return rc->query(pos, mid+1, r) + lc->sum;
}
};
vector<node> rt;
int rtpos[maxn];
int gt(int a, int b){
if(b == 0)return 0;
return rt[rtpos[a]].query(b);
}
int gt_gap(int l, int r){
if(l > r)return 0;
if(r-l < precalc[l].size())return precalc[l][r-l];
if(mp.find({l, r}) != mp.end())return mp[{l, r}];
int re = pfx_all[r] - gt(r, l-1);
mp[{l, r}] = re;
return re;
}
void init(int N, int A[], int B[]) {
n = N;
for(int i = 0; i < n; i++){
L[i] = A[i];
R[i] = B[i];
pos[R[i]].push_back(L[i]);
for(int x = B[i]; x <= n; x += x&(-x))d[x].push_back(A[i]);
pfx_all[B[i]]++;
sfx_all[A[i]]++;
}
for(int i = 1; i <= n; i++){
pfx_all[i] += pfx_all[i-1];
sort(pos[i].begin(), pos[i].end());
d[i].push_back(-1);
sort(d[i].begin(), d[i].end());
d[i].erase(unique(d[i].begin(), d[i].end()), d[i].end());
FW[i].assign(d[i].size(), 0);
}
for(int i = 1; i <= n; i++){
int crr = 0;
for(int j = 0; j + i <= n && j < n/i; j++){
crr += pos[i+j].end() - lower_bound(pos[i+j].begin(), pos[i+j].end(), i);
precalc[i].push_back(crr);
}
}
for(int i = n; i >= 1; i--)sfx_all[i] += sfx_all[i+1];
rt.push_back(node());
rt.back().build();
for(int i = 1; i <= n; i++){
for(auto v: pos[i]){
node nw;
nw.upd(rt.back(), v);
rt.push_back(nw);
}
rtpos[i] = rt.size()-1;
}
for(int i = 1; i <= n; i++){
for(int j = 1; j < FW[i].size(); j++)FW[i][j] += FW[i][j-1];
}
}
int can(int M, int K[]) {
long long sum = 0;
sort(K, K+M);
vector<pair<int, int>> vec;
for(int i = 0; i < M; i++){
sum += K[i];
if(vec.empty() || vec.back().first != K[i])vec.push_back({K[i], 1});
else vec.back().second++;
}
if(sum > n)return 0;
for(int i = 0; i < vec.size(); i++){
dp[i] = vec[i].first*vec[i].second + pfx_all[vec[i].first-1];
for(int j = 0; j < i; j++){
dp[i] = max(dp[i], dp[j] + vec[i].first*vec[i].second + gt_gap(vec[j].first+1,vec[i].first-1));
}
sum -= vec[i].first*vec[i].second;
if(dp[i] + sum > n)return 0;
if(dp[i] + sfx_all[vec[i].first+1] > n)return 0;
}
return 1;
// sum_segment - sum_M < 0 => bad
// sum_segment = pfx_all - sumgap
}
