#include "meetings.h"
#include <cstring>
#include <cstdio>
#include <stack>
#include <algorithm>
template<typename T> bool ckmin(T& a, const T& b) {return b<a?a=b,1:0;}
template<typename T> bool ckmax(T& a, const T& b) {return b>a?a=b,1:0;}
using ll = long long;
const ll INF = 0x3f3f3f3f3f3f3f3f;
std::vector<int> H;
int N;
ll brute(int L, int R)
{
std::vector<ll> bl, br;
bl.reserve(R-L), br.reserve(R-L);
int len = R-L;
{
std::stack<int> s; s.push(L-1);
ll cur=0;
for(int i=L;i<R;++i)
{
cur += H[i];
for(;s.size()>1 && H[i] > H[s.top()];)
{
int pr=s.top();
s.pop();
cur += (ll)(pr-s.top())*(H[i]-H[pr]);
}
bl.push_back(cur);
s.push(i);
}
}
{
std::stack<int> s; s.push(R);
ll cur=0;
for(int i=R-1;i>=L;--i)
{
cur += H[i];
for(;s.size()>1 && H[i] > H[s.top()];)
{
int pr=s.top();
s.pop();
cur += (ll)(s.top()-pr)*(H[i]-H[pr]);
}
br.push_back(cur);
s.push(i);
}
}
ll ans=INF;
for(int i=0;i<len;++i)
ckmin(ans, bl[i]+br[len-1-i]-H[L+i]);
return ans;
}
const int MH = 20;
struct stval
{
public:
int vl[MH], vr[MH], ul[MH], ur[MH]; //v = I have the target, u = you have the target
int max;
stval()
{
memset(vl, 0, sizeof vl);
memset(vr, 0, sizeof vr);
memset(ul, 0, sizeof ul);
memset(ur, 0, sizeof ur);
max=0;
}
stval(int _n)
{
max = _n;
for(int i=0;i<max;++i)
vl[i]=vr[i]=max;
for(int i=0;i<MH;++i)
ul[i]=ur[i]=std::max(max, i);
}
/*
stval& operator += (const stval& o)
{
for(int i=0;i<max;++i)
vl[i] += o.ul[max];
for(int i=max;i<o.max;++i)
vl[i] = ur[i]+o.vl[i];
for(int i=0;i<o.max;++i)
vr[i] = o.vr[i]+ur[o.max];
for(int i=o.max;i<max;++i)
vr[i] += o.ul[max];
for(int i=0;i<MH;++i)
ul[i] += o.ul[std::max(max, i)];
for(int i=0;i<MH;++i)
ur[i] = o.ur[i] + ur[std::max(o.max, i)];
ckmax(max, o.max);
return *this;
}
*/
friend stval operator + (const stval& a, const stval& b)
{
stval f;
for(int i=0;i<a.max;++i)
f.vl[i] = a.vl[i] + b.ul[a.max];
for(int i=a.max;i<b.max;++i)
f.vl[i] = a.ur[i] + b.vl[i];
if(a.max < b.max)
for(int i=0;i<a.max;++i)
ckmin(f.vl[a.max], a.vr[i] + b.ul[i]);
for(int i=0;i<b.max;++i)
f.vr[i] = b.vr[i] + a.ur[b.max];
for(int i=b.max;i<a.max;++i)
f.vr[i] = b.ul[i] + a.vr[i];
if(b.max < a.max)
for(int i=0;i<b.max;++i)
ckmin(f.vr[b.max], b.vl[i] + a.ur[i]);
for(int i=0;i<MH;++i)
f.ul[i] = a.ul[i] + b.ul[std::max(i, a.max)];
for(int i=0;i<MH;++i)
f.ur[i] = b.ur[i] + a.ur[std::max(i, b.max)];
f.max = std::max(a.max, b.max);
return f;
}
};
stval st[1 << 18];
void build(int n, int l, int r)
{
if(r-l>1)
{
int m=l+(r-l)/2;
build(n<<1, l, m);
build(n<<1|1, m, r);
st[n]=st[n<<1]+st[n<<1|1];
}
else
st[n]=stval(H[l]);
}
stval qv;
void qry(int n, int l, int r, int ql, int qr)
{
if(ql <= l&&r <= qr)
qv = qv + st[n];
else
{
int m=l+(r-l)/2;
if(ql < m) qry(n<<1, l, m, ql, qr);
if(m < qr) qry(n<<1|1, m, r, ql, qr);
}
}
std::vector<long long> minimum_costs(std::vector<int> _H, std::vector<int> L,
std::vector<int> R) {
H = _H;
N = H.size();
int maxh = *std::max_element(H.begin(), H.end());
if(maxh <= 20)
{
for(int& x:H) --x;
build(1, 0, N);
}
int Q = L.size();
std::vector<ll> C(Q);
for (int j = 0; j < Q; ++j)
{
if(maxh <= 20)
{
qv = stval();
qry(1, 0, N, L[j], R[j]+1);
//printf("\t%d\n", qv.vl[3]);
C[j]=qv.max*(R[j]-L[j]+1);
for(int i=0;i<qv.max;++i)
ckmin(C[j], (ll)std::min(qv.vl[i], qv.vr[i]));
C[j]+=(R[j]-L[j]+1);
}
else
C[j]=brute(L[j], R[j]+1);
}
return C;
}
