#include <bits/stdc++.h>
#include "meetings.h"
using namespace std;
#define X first
#define Y second
#define pb push_back
typedef pair<int, int> ii;
typedef long long ll;
const int maxn = 750005;
const int maxv = 25;
int arr[maxn];
int n, q;
vector<int> buck[maxv];
struct segtree
{
int sz;
struct node
{
ll val;
node *left, *right;
node(ll _val = 0, node* _left = NULL, node* _right = NULL)
{
val = _val; left = _left; right = _right;
}
node* build(vector<ll> &vals, int L, int R)
{
if(L == R)
{
return new node(vals[L], NULL, NULL);
}
int M = (L+R)/2;
node* x = build(vals, L, M);
node* y = build(vals, M+1, R);
return new node(min(x->val, y->val), x, y);
}
ll ask(int i, int j, int L, int R)
{
if(i> R || j< L) return 4e18;
if(i<= L && R<= j) return val;
int M = (L+R)/2;
ll x = left->ask(i, j, L, M);
ll y = right->ask(i, j, M+1, R);
return min(x, y);
}
};
node *root;
segtree(){}
segtree(vector<ll> &vals)
{
sz = vals.size();
root = root->build(vals, 0, sz-1);
}
ll ask(int i, int j)
{
return root->ask(i, j, 0, sz-1);
}
};
struct cart
{
ll val;
vector<cart*> ptr; //size k+1
vector<int> poles; //size k
vector<ll> cand; //size k+1
segtree seg;
cart(){}
cart(int L, int R, int H)
{
if(L> R)
{
val = 0;
return;
}
int lo = lower_bound(buck[H].begin(), buck[H].end(), L)-buck[H].begin();
int hi = upper_bound(buck[H].begin(), buck[H].end(), R)-buck[H].begin()-1;
for(int i = lo; i<= hi; i++)
{
poles.pb(buck[H][i]);
}
ptr.resize(poles.size()+1);
cand.resize(poles.size()+1);
for(int i = 0; i< (int) ptr.size(); i++)
{
int sai = (i?poles[i-1]+1:L);
int kwa = (i< poles.size()?poles[i]-1:R);
// printf("[%d %d] %d (%d)to [%d %d] %d\n", L, R, H, i, sai, kwa, H-1);
ptr[i] = new cart(sai, kwa, H-1);
cand[i] = ptr[i]->val;
cand[i] -= 1LL*(kwa-sai+1)*H;
}
seg = segtree(cand);
val = min(seg.ask(0, seg.sz-1)+1LL*(R-L+1)*H, 1LL*(R-L+1)*H);
// printf("[%d %d] %d = %lld\n", L, R, H, val);
}
ll ask(int i, int j, int L = 0, int R = n-1, int H = 21)
{
if(L> R|| i> R || j< L) return 0;
// printf("asking %d %d %d\n", L, R, H);
if(i<= L && R<= j)
{
// printf("= %lld\n", val);
return val;
}
int sai = lower_bound(poles.begin(), poles.end(), i)-poles.begin();
int kwa = upper_bound(poles.begin(), poles.end(), j)-poles.begin()-1;
if(sai> kwa)
{
int tahm = (sai?poles[sai-1]+1:L);
int kench = (sai< poles.size()?poles[sai]-1:R);
return ptr[sai]->ask(i, j, tahm, kench, H-1);
}
// if(sai == kwa) printf("sai = kwa! [%d]\n", poles[sai]);
// printf("for [%d %d]\n", L, R);
ll x = ptr[sai]->ask(i, poles[sai]-1, sai?poles[sai-1]+1:L, poles[sai]-1, H-1)-1LL*(poles[sai]-i)*H;
// printf("x = %lld\n", x);
ll mid = seg.ask(sai+1, kwa);
ll y = ptr[kwa+1]->ask(poles[kwa]+1, j, poles[kwa]+1, kwa+1<poles.size()?poles[kwa+1]-1:R, H-1)-1LL*(j-poles[kwa])*H;
// printf("y = %lld\n", y);
return min(min(0LL, mid), min(x, y)) + 1LL*(j-i+1)*H;
}
};
cart foo;
vector<ll> minimum_costs(vector<int> H, vector<int> L, vector<int> R)
{
n = H.size(); q = L.size();
for(int i = 0; i< n; i++) arr[i] = H[i];
for(int i = 0; i< n; i++)
{
buck[arr[i]].pb(i);
}
foo = cart(0, n-1, 21);
vector<ll> ans(q);
for(int i = 0; i< q; i++)
{
ans[i] = foo.ask(L[i], R[i]);
assert(ans[i]> 0);
}
return ans;
}
