#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;
int n, q;
struct rng
{
int ed;
ll m, b;
rng(int _ed = 0, ll _m = 0, ll _b = 0) : ed(_ed), m(_m), b(_b){}
ll eval(int x)
{
return m*x+b;
}
};
map<int, rng> png;
int arr[maxn];
int st[4*maxn];
void build(int p = 1, int L = 0, int R = n-1)
{
if(L == R)
{
st[p] = L;
return;
}
int M = (L+R)/2;
build(2*p, L, M);
build(2*p+1, M+1, R);
if(arr[st[2*p]]>= arr[st[2*p+1]]) st[p] = st[2*p];
else st[p] = st[2*p+1];
}
int rmq(int i, int j, int p = 1, int L = 0, int R = n-1)
{
if(i> R || j< L) return -1;
if(i<= L && R<= j) return st[p];
int M = (L+R)/2;
int x = rmq(i, j, 2*p, L, M);
int y = rmq(i, j, 2*p+1, M+1, R);
if(x == -1) return y;
if(y == -1) return x;
return (arr[x]>= arr[y])?x:y;
}
void build2(int p = 1, int L = 0, int R = n-1)
{
if(L == R)
{
st[p] = L;
return;
}
int M = (L+R)/2;
build2(2*p, L, M);
build2(2*p+1, M+1, R);
if(arr[st[2*p]]> arr[st[2*p+1]]) st[p] = st[2*p];
else st[p] = st[2*p+1];
}
int rmq2(int i, int j, int p = 1, int L = 0, int R = n-1)
{
if(i> R || j< L) return -1;
if(i<= L && R<= j) return st[p];
int M = (L+R)/2;
int x = rmq2(i, j, 2*p, L, M);
int y = rmq2(i, j, 2*p+1, M+1, R);
if(x == -1) return y;
if(y == -1) return x;
return (arr[x]> arr[y])?x:y;
}
vector<int> tree[maxn];
vector<ii> ql[maxn];
vector<ii> qr[maxn];
ll ansl[maxn];
ll ansr[maxn];
int cartesian(int L, int R)
{
if(L> R) return -1;
int u = rmq(L, R);
int x = cartesian(L, u-1);
int y = cartesian(u+1, R);
if(x != -1) tree[u].pb(x);
if(y != -1) tree[u].pb(y);
return u;
}
int cartesian2(int L, int R)
{
if(L> R) return -1;
int u = rmq2(L, R);
int x = cartesian2(L, u-1);
int y = cartesian2(u+1, R);
if(x != -1) tree[u].pb(x);
if(y != -1) tree[u].pb(y);
return u;
}
pair<int, int> cov[maxn];
ll lz[maxn];
int sz[maxn];
int arx[maxn];
void solve(int u, vector<ii> *quest, ll *answ)
{
int lc = -1, rc = -1;
if(tree[u].size() == 2)
{
lc = tree[u][0];
rc = tree[u][1];
}
else if(tree[u].size() == 1)
{
if(tree[u][0]< u) lc = tree[u][0];
else rc = tree[u][0];
}
cov[u] = {u, u};
if(lc != -1)
{
solve(lc, quest, answ);
cov[u].X = min(cov[u].X, cov[lc].X);
}
if(rc != -1)
{
solve(rc, quest, answ);
cov[u].Y = max(cov[u].Y, cov[rc].Y);
}
rng here;
ll midcost;
if(lc == -1)
{
midcost = arr[u];
}
else
{
auto it = png.upper_bound(u);
--it;
midcost = arr[u]+(it->second).eval(u-1)+lz[lc];
}
here = rng(u, 0, midcost);
png[u] = here;
// printf("midcost[%d] = %lld\n", u, midcost);
// printf("solving %d\n", u);
if(rc != -1)
{
ll add = 1LL*(u-cov[u].X+1)*arr[u];
lz[rc] += add;
int st = u+1;
bool fixed = false;
while(st<= cov[u].Y)
{
// printf("%d\n", st);
rng f2 = png[st];
int ed = f2.ed;
rng f1 = rng(0, arr[u], midcost-1LL*arr[u]*u);
if(f1.eval(ed)<= f2.eval(ed)+lz[rc])
{
// printf("this case\n");
png.erase(st);
st = ed+1;
sz[rc]--;
}
else
{
// printf("bad at %d\n", st);
int lo = st, hi = ed;
while(lo< hi)
{
int mid = (lo+hi)/2;
// printf("%d\n", mid);
if(f1.eval(mid)<= f2.eval(mid)+lz[rc]) lo = mid+1;
else hi = mid;
}
// printf("first to okay: %d\n", lo);
png.erase(st);
sz[rc]--;
if(u+1<= lo-1)
{
png[u+1] = rng(lo-1, arr[u], midcost-1LL*arr[u]*u-lz[rc]);
// printf("{%d, %d} left fuction\n", u+1, lo-1);
sz[rc]++;
}
// else printf("WTF\n");
png[lo] = f2;
sz[rc]++;
fixed = true;
break;
}
}
// printf("fixed = %d\n", fixed);
if(!fixed)
{
// printf("{%d, %d} left function\n", u+1, cov[u].Y);
png[u+1] = rng(cov[u].Y, arr[u], midcost-1LL*arr[u]*u-lz[rc]);
sz[rc]++;
}
}
if(lc != -1 && rc != -1)
{
if(sz[lc]< sz[rc])
{
int st = cov[u].X;
while(st< u)
{
png[st].b += lz[lc]-lz[rc];
st = png[st].ed+1;
}
png[u].b -= lz[rc];
lz[u] = lz[rc];
}
else
{
int st = u+1;
while(st<= cov[u].Y)
{
png[st].b += lz[rc]-lz[lc];
st = png[st].ed+1;
}
png[u].b -= lz[lc];
lz[u] = lz[lc];
}
}
else if(lc != -1)
{
png[u].b -= lz[lc];
lz[u] = lz[lc];
}
else
{
png[u].b -= lz[rc];
lz[u] = lz[rc];
}
sz[u] = 1;
if(lc != -1) sz[u] += sz[lc];
if(rc != -1) sz[u] += sz[rc];
for(auto kk : quest[u])
{
int want = kk.X, id = kk.Y;
auto it = png.upper_bound(want);
--it;
answ[id] = (it->second).eval(want)+lz[u];
}
// printf("rangeL(%d) = %d\n", u, cov[u].X);
// for(int i = cov[u].X; i<= cov[u].Y; i++)
// {
// auto it = png.upper_bound(i);
// --it;
// // printf("using %d\n", it->first);
// printf("cost[rangeL(%d), %d] = %lld\n", u, i, (it->second).eval(i)+lz[u]);
// }
}
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];
build();
int root = cartesian(0, n-1);
for(int i = 0; i< q; i++)
{
int arg = rmq(L[i], R[i]);
arx[i] = arg;
if(arg+1<= R[i])
{
int argr = rmq(arg+1, R[i]);
qr[argr].pb(ii(R[i], i));
}
if(L[i]<= arg-1)
{
int argl = rmq(L[i], arg-1);
ql[n-argl-1].pb(ii(n-L[i]-1, i));
// printf("ql[%d] pb %d\n", n-argl-1, n-L[i]-1);
}
}
// printf("finished\n");
solve(root, qr, ansr);
memset(lz, 0, sizeof lz);
memset(cov, 0, sizeof cov);
memset(sz, 0, sizeof sz);
for(int i = 0; i< n; i++) tree[i].clear();
png.clear();
for(int i = 0; i< n; i++) arr[i] = H[n-i-1];
build2();
root = cartesian2(0, n-1);
solve(root, ql, ansl);
for(int i = 0; i< n; i++) arr[i] = H[i];
vector<ll> ret(q);
for(int i = 0; i< q; i++)
{
// printf("ansl[%d] = %lld, ansr[%d] = %lld\n", i, ansl[i], i, ansr[i]);
ret[i] = min(ansl[i]+1LL*(R[i]-arx[i]+1)*arr[arx[i]], ansr[i]+1LL*(arx[i]-L[i]+1)*arr[arx[i]]);
}
return ret;
}
