#include "teams.h"
#include <bits/stdc++.h>
#define f first
#define s second
#define pb push_back
using namespace std;
const int N = 3e5 + 5;
int tree[10*N],le_[10*N], ri_[10*N];
int cur,root[N],prevroot,dp[N],m,a[N],b[N],k[N],n,cnt;
vector <int> v[N];
int merge(int a, int b) {
return a + b;
}
void build(int node, int le, int ri) {
// cout<<le<<" "<<ri<<" "<<node<<endl;
if (le == ri) {
tree[node] = 0;
return ;
}
cur++;
le_[node] = cur;
cur++;
ri_[node] = cur;
int mid = (le + ri) / 2;
build(le_[node],le,mid);
build(ri_[node],mid + 1, ri);
tree[node] = merge(tree[le_[node]], tree[ri_[node]]);
}
void update(int node, int le, int ri, int idx, int val) {
if (le > idx || ri < idx) return ;
if (le == ri) {
//cout<<cur<<" "<<val<<endl;
tree[cur] = tree[node] + val;
//cout<<cur<<" "<<le<<" "<<ri<<" "<<tree[cur]<<endl;
return ;
}
int mid = (le + ri) / 2;
int x = cur;
cur++;
le_[x] = le_[node];
ri_[x] = ri_[node];
if (idx <= mid) {
le_[x] = cur;
} else ri_[x] = cur;
update(le_[node], le,mid,idx,val);
update(ri_[node], mid + 1, ri, idx,val);
tree[x] = merge(tree[le_[x]], tree[ri_[x]]);
//cout<<x<<" "<<le<<" "<<ri<<" "<<tree[x]<<endl;
}
int getans(int node, int le, int ri, int start, int end) {
if (le > end || ri < start) return 0;
if (le >= start && ri <= end) {
return tree[node];
}
int mid = (le + ri) / 2;
return merge(getans(le_[node],le,mid,start,end), getans(ri_[node],mid + 1,ri,start,end));
}
int can(int M, int K[]) {
m = M;
for (int i = 1; i <= m; i++) {
dp[i] = 1e9;
k[i] = K[i - 1];
}
int sum = 0;
for (int i = 1; i <= m; i++) {
sum += k[i];
}
if (sum > n) {
return 0;
}
sort(k + 1, k + m + 1);
dp[0] = 0;
for (int i = 1; i <= m; i++) {
for (int j = i - 1; j >= 0; j--) {
// k[j]+1 -----> k[i] shualedshi >= k[i]
cnt = getans(root[k[i]],1,n,k[i],n) - getans(root[k[j]],1,n,k[i],n);
dp[i] = min(dp[i],dp[j] + cnt - k[i]);
//cout<<i<<" "<<j<<" "<<dp[j]<<" "<<cnt<<endl;
if (dp[i] < 0) {
return 0;
}
}
//cout<<i<<" "<<dp[i]<<endl;
}
return 1;
}
void init(int N, int A[], int B[]) {
n = N;
for (int i = 1; i <= n; i++) {
a[i] = A[i - 1]; b[i] = B[i - 1];
v[a[i]].pb(b[i]);
}
cur = 1; root[0] = 1;
build(1,1,n);
for (int i = 1; i <= n; i++) {
prevroot = root[i - 1];
root[i] = root[i - 1];
for (int j = 0; j < v[i].size(); j++) {
cur++;
root[i] = cur;
update(prevroot, 1,n,v[i][j],1);
prevroot = root[i];
}
}
dp[0] = 0;
}
