//codigo Yan
#include <bits/stdc++.h>
#define ff first
#define ss second
#define MAX 500010
#define OO 1000000010
using namespace std;
typedef pair<int,int> pii;
class PersistentSegTree
{
public:
void build(int i)
{
e.push_back(e[i]);
d.push_back(d[i]);
s.push_back(s[i]);
}
int update(int id, int ini, int fim, int i)
{
int novo = ++node_cur;
build(id);
if(ini == fim)
{
s[novo]++;
return novo;
}
int m = (ini + fim)/2;
if(i <= m)
{
int aux = update(e[novo] , ini , m , i);
e[novo] = aux;
}
else
{
int aux = update(d[novo] , m + 1 , fim , i);
d[novo] = aux;
}
s[novo] = s[e[novo]] + s[d[novo]];
return novo;
}
int query(int id , int ini , int fim , int i, int j)
{
if(id == 0 || ini > j || fim < i) return 0;
if(i <= ini && fim <= j) return s[id];
int m = (ini + fim)/2;
return query(e[id] , ini , m , i , j) + query(d[id] , m + 1 , fim , i , j);
}
int bs(int r1, int r2 , int ini , int fim , int v)
{
if(ini == fim) return ini;
int b = s[e[r2]] - s[e[r1]];
int m = (ini + fim)/2;
if(b >= v) return bs(e[r1] , e[r2] , ini , m , v);
return bs(d[r1] , d[r2] , m + 1 , fim , v - b);
}
PersistentSegTree()
{
e.push_back(0); e.push_back(0);
d.push_back(0); d.push_back(0);
s.push_back(0); s.push_back(0);
}
private:
vector<int> e, d;
vector<int> s;
int node_cur = 1;
} SEG;
int n;
int root[MAX];
pii points[MAX];
int rectangle_sum(int x1, int x2, int y1, int y2)
{
int s1 = SEG.query(root[x2] , 0 , n , y1 , y2);
int s2 = SEG.query(root[x1 - 1] , 0 , n , y1 , y2);
return s1 - s2;
}
class bars
{
public:
int l, r, h;
int corner;
bars(int ll, int rr, int hh, int cc)
{
l = ll;
r = rr;
h = hh;
corner = cc;
}
};
class pilha
{
public:
bool push(int i, int h)
{
bars k(i , i , h , 0);
while(h >= p.back().h)
{
k.l = p.back().l;
p.pop_back();
}
int s = i;
while(!p.empty())
{
int ll = p.back().l;
int lr = p.back().r;
int lh = p.back().h;
int lc = p.back().corner;
int rs = rectangle_sum(lr + 1 , k.r , k.h + 1 , lh);
if(rs > s)
{
int nh = SEG.bs(root[lr] , root[k.r] , 0 , n , s + rectangle_sum(lr + 1 , k.r , 0 , k.h));
int tot = rectangle_sum(lr + 1 , k.r , k.h + 1 , nh);
k.h = nh;
k.l = lr + 1;
k.corner = tot - s;
p.push_back(k);
return true;
}
k.l = ll;
k.h = lh;
p.pop_back();
if(rs <= s && s <= rs + lc)
{
k.corner = lc - (s - rs);
p.push_back(k);
return true;
}
s -= rs + lc;
}
return false;
}
void clear()
{
p.clear();
bars k(-OO , 0 , OO , 0);
p.push_back(k);
}
pilha()
{
bars k(-OO , 0 , OO , 0);
p.push_back(k);
}
private:
vector<bars> p;
};
void init(int N, int A[], int B[])
{
n = N;
for(int g = 0 ; g < n ; g++) points[g].ff = A[g];
for(int g = 0 ; g < n ; g++) points[g].ss = B[g];
sort(points , points + n);
int i = 0;
root[0] = 1;
for(int g = 1 ; g <= n ; g++)
{
root[g] = root[g - 1];
while(i < n && points[i].ff == g)
{
int aux = SEG.update(root[g] , 0 , n , points[i].ss);
root[g] = aux;
i++;
}
}
}
int can(int M, int K[])
{
sort(K , K + M);
bool error = true;
pilha s;
for(int g = 0 ; g < M && error ; g++) error = error && s.push(K[g] , K[g] - 1);
return (error) ? 1 : 0;
}
