#include "teams.h"
#include <bits/stdc++.h>
using namespace std;
using ii = pair<int, int>;
using ll = long long;
#define X first
#define Y second
struct SegmentTree {
int lv;
int n;
vector<int> x[1100007], gel[1100007], lel[1100007], ger[1100007], ler[1100007];
int y[600007];
SegmentTree(int n, int A[], int B[]) {
lv = 2;
this->n = n;
while(lv < n + 2)
lv *= 2;
vector<ii> V(n);
for(int i = 0 ; i < n ; i++)
V[i] = {B[i], A[i]};
sort(V.begin(), V.end());
for(int i = 0 ; i < n ; i++) {
y[i] = V[i].X;
x[lv + i].push_back(V[i].Y);
}
for(int i = lv - 1 ; i >= 1 ; i--) {
int l = 2 * i;
int r = 2 * i + 1;
x[i].resize(x[l].size() + x[r].size());
merge(x[l].begin(), x[l].end(), x[r].begin(), x[r].end(), x[i].begin());
int ind;
ind = 0;
gel[i].resize(x[i].size());
for(int j = 0 ; j < x[i].size() ; j++) {
while(ind < x[l].size() && x[l][ind] < x[i][j])
ind++;
gel[i][j] = ind;
}
ind = 0;
ger[i].resize(x[i].size());
for(int j = 0 ; j < x[i].size() ; j++) {
while(ind < x[r].size() && x[r][ind] < x[i][j])
ind++;
ger[i][j] = ind;
}
ind = -1;
lel[i].resize(x[i].size());
for(int j = 0 ; j < x[i].size() ; j++) {
while(ind + 1 < x[l].size() && x[l][ind + 1] <= x[i][j])
ind++;
lel[i][j] = ind;
}
ind = -1;
ler[i].resize(x[i].size());
for(int j = 0 ; j < x[i].size() ; j++) {
while(ind + 1 < x[r].size() && x[r][ind + 1] <= x[i][j])
ind++;
ler[i][j] = ind;
}
}
}
int query(int a, int b, int l, int r, int w, int i1, int i2) {
//~ cout << "q" << l << " " << r << " " << i1 << " " << i2 << endl;
if(b < l || a > r || l > r || i1 > i2)
return 0;
if(a <= l && r <= b)
return i2 - i1 + 1;
return query(a, b, l, (l + r) / 2, 2 * w, gel[w][i1], lel[w][i2])
+ query(a, b, (l + r) / 2 + 1, r, 2 * w + 1, ger[w][i1], ler[w][i2]);
}
int count(int x1, int x2, int y1, int y2) {
//~ cout << x1 << " " << x2 << " " << y1 << " "<< y2 << endl;
int a = lower_bound(y, y + n, y1) - y;
int b = upper_bound(y, y + n, y2) - y - 1;
if(a > b)
return 0;
int l = 0;
int r = lv - 1;
int w = 1;
int i1 = lower_bound(x[w].begin(), x[w].end(), x1) - x[w].begin();
int i2 = upper_bound(x[w].begin(), x[w].end(), x2) - x[w].begin() - 1;
//~ cout << a << " " << b << " " << i1 << " " << i2 << " " << query(a, b, l, r, w, i1, i2) << endl;
return query(a, b, l, r, w, i1, i2);
}
int query2(int l, int r, int w, ll maxv, int i1, int i2) {
//~ cout << l << " " << r << " " << maxv << " " << i1 << " " << i2 << endl;
if(maxv < 0)
return 1e9;
if(i1 > i2)
return 0;
if(l == r)
return y[l];
if(ler[w][i2] - ger[w][i1] + 1 <= maxv)
return query2(l, (l + r) / 2, 2 * w, maxv - max(0, ler[w][i2] - ger[w][i1] + 1), gel[w][i1], lel[w][i2]);
return query2((l + r) / 2 + 1, r, 2 * w + 1, maxv, ger[w][i1], ler[w][i2]);
}
int find_y(int x1, int x2, ll maxv) {
int i1 = lower_bound(x[1].begin(), x[1].end(), x1) - x[1].begin();
int i2 = upper_bound(x[1].begin(), x[1].end(), x2) - x[1].begin() - 1;
//~ cout << x1 << " " << x2 << " " << maxv << " " << query2(0, lv - 1, 1, maxv, i1, i2) << endl;
return query2(0, lv - 1, 1, maxv, i1, i2);
}
};
SegmentTree *ST;
void init(int N, int A[], int B[]) {
ST = new SegmentTree(N, A, B);
}
ll dp[200007];
int can(int M, int K[]) {
//~ cout << "hi" << endl;
sort(K, K + M);
set<int> cand;
set<ii> Q;
dp[0] = 0;
cand.insert(0);
vector<ii> V;
V.emplace_back(0, 0);
for(int i = 0 ; i < M ; i++) {
int k = K[i];
if(V.empty() || V.back().X != k)
V.emplace_back(k, 1);
else
V.back().Y++;
}
ll res = 1e18;
for(int i = 1 ; i < V.size() ; i++) {
while(!Q.empty() && Q.begin()->X < V[i].X) {
//~ for(int x : cand)
//~ cout << x << " ";
//~ cout << endl;
int j = Q.begin()->Y;
//~ cout << j << endl;
Q.erase(Q.begin());
auto it = cand.lower_bound(j);
if(it == cand.end() || *it != j)
continue;
cand.erase(next(it));
if(next(it) != cand.end()) {
int k = *next(it);
Q.insert({ST->find_y(V[j].X + 1, V[k].X, dp[k] - dp[j]), j});
}
}
int j = *prev(cand.end());
dp[i] = dp[j] + ST->count(V[j].X + 1, V[i].X, V[i].X, 1e9) - (ll)V[i].X * V[i].Y;
res = min(res, dp[i]);
//~ cout << i << " " << j << " " << dp[i] << endl;
Q.insert({ST->find_y(V[j].X + 1, V[i].X, dp[i] - dp[j]), j});
//~ cout << ST->find_y(V[j].X + 1, V[i].X, dp[i] - dp[j]) << endl;
cand.insert(i);
}
return res >= 0;
}
