/**
* user: ppavic
* fname: Patrik
* lname: Pavić
* task: teams
* score: 100.0
* date: 2019-06-25 17:32:34.665190
*/
#include "teams.h"
#include <algorithm>
#include <vector>
#include <set>
#include <cstdio>
#include <cstring>
#define PB push_back
#define X first
#define Y second
using namespace std;
typedef pair < int, int > pii;
typedef vector < int > vi;
typedef vector < pii > vp;
typedef long long ll;
typedef short int sint;
const int N = 5e5 + 500;
const int OFF = (1 << 19);
struct node{
node* L;
node* R;
int sm;
//int a, b, i;
};
node* root[N];
set < pii > ss;
void build(int i, node* x){
if(i >= 2 * OFF) return;
x -> L = new node(); x -> R = new node(); x -> sm = 0;
build(2 * i, x -> L);
build(2 * i + 1, x -> R);
}
void update(int a,int b,int c,node *x){
if(a == b) return;
if(c <= (a + b) / 2){
node* y = new node();
y -> sm = x -> L -> sm + 1;
y -> L = x -> L -> L;
y -> R = x -> L -> R;
x -> L = y;
update(a, (a + b) / 2, c, x -> L);
return;
}
else{
node* y = new node();
y -> sm = x -> R -> sm + 1;
y -> L = x -> R -> L;
y -> R = x -> R -> R;
x -> R = y;
update((a + b) / 2 + 1, b, c, x -> R);
return;
}
}
int sp = -1;
int n, D[N], k[N], q, m, lst = 0, tez[N], mrt[N], lg[N];
set < int > s;
vi izb[N];
int W(int i,node* x1,node* x2,int k){
if(i >= OFF) return i - OFF;
int x = x2 -> R -> sm - x1 -> R -> sm;
if(x >= k)
return W(2 * i + 1, x1 -> R, x2 -> R, k);
return W(2 * i, x1 -> L, x2 -> L, k - x);
}
int Z(int a,int b,int lo,int hi,node* x1){
if(lo <= a && b <= hi) return (x1 -> sm);
if(a > hi || b < lo) return 0;
//printf("z %d %d res : %d - %d\n", a, b, (x2 -> sm), (x1 -> sm));
return Z(a, (a + b) / 2, lo, hi, x1 -> L) + Z((a + b) / 2 + 1, b, lo, hi, x1 -> R);
}
void izbaci(int x){
//if(q == sp)printf("izbacujem %d\n", x);
s.erase(x);
auto it1 = s.lower_bound(x);
if(it1 == s.end() || it1 == s.begin()) return;
int j = *it1, i = *(--it1);
if(D[j] < D[i]) return;
int kad = W(1, root[k[i]], root[k[j]], D[j] - D[i]);
//if(q == sp) printf("eksluzivno!! izbaci me {i = %d j = %d} u %d trebam %d\n", i, j, kad, D[j] - D[i]);
kad++;
if(kad <= k[m - 1] && kad > lst) ss.insert({kad, j});
}
void init(int nn, int a[], int b[]) {
n = nn;
vector < pii > v;
for(int i = 0;i < n;i++){
v.PB({a[i], b[i]});
}
sort(v.begin(), v.end());
int j = 0;
root[0] = new node();
build(1, root[0]);
for(int i = 1;i <= n;i++){
root[i] = new node();
root[i] -> sm = root[i - 1] -> sm;
root[i] -> L = root[i - 1] -> L;
root[i] -> R = root[i - 1] -> R;
while(j < v.size() && v[j].X == i){
update(0, OFF - 1, v[j++].Y, root[i]);
root[i] -> sm++;
}
}
}
int can(int mm, int kk[]) {
q++; m = 1;
sort(kk, kk + mm);
k[0] = kk[0], tez[0] = 1;
for(int i = 1;i < mm;i++) {
if(kk[i] == k[m - 1]){
tez[m - 1]++;
}
else{
k[m] = kk[i], tez[m++] = 1;
}
}
s.clear();
int ans = 0;
lst = 0;
for(int i = 0;i < m;i++){
for(; !ss.empty() && ss.begin()->X <= k[i]; ){
izbaci(ss.begin() -> Y);
ss.erase(ss.begin());
}
int ubac = 1;
D[i] = Z(0, OFF - 1, k[i], OFF - 1, root[k[i]]) - tez[i] * k[i];
//printf("prije %d\n", D[i]);
for(int j = 0;j < i;j++){
}
if(!s.empty()){
int j = *s.rbegin();
//if(q == sp)printf("tu sam %d\n", k[j]);
D[i] = min(D[i], D[j] + Z(0, OFF - 1, k[i], OFF - 1, root[k[i]]) - Z(0, OFF - 1, k[i], OFF - 1, root[k[j]]) - tez[i] * k[i]);
if(D[i] > D[j]){
int kad = W(1, root[k[j]], root[k[i]], D[i] - D[j]);
kad++;
if(kad <= k[i]) ubac = 0;
else if(kad <= k[m - 1]) ss.insert({kad, i});
}
}
if(ubac) s.insert(i);
ans = min(ans, D[i]);
}
ss.clear();
return ans >= 0;
}
