#include "meetings.h"
#include <vector>
#include <algorithm>
#include <iostream>
#include <deque>
#include <cassert>
using namespace std;
using ll = long long;
using vll = vector<ll>;
using vi = vector<int>;
using pii = pair<int, int>;
#define sz(x) (int(x.size()))
const int mx = 750'000;
const ll INF = 1'000'000'000'000'000'000LL;
int N;
int Q;
vi H;
vi L, R;
vi M(mx);
vi peak_queries[mx];
vi HD;
vi lc, rc;
vi le, re;
vll ans;
const int e20 = (1<<20);
struct segtree
{
// int l;
// int r;
vector<pii> v = vector<pii>(2*e20, {-1, -1});
// pii v[2*e20];
// segtree* left = NULL;
// segtree* right = NULL;
segtree()
{
;
}
void build_segtree(int L, int R, vi& Z)
{
// cerr << "build segtree " << L << ' ' << R << '\n';
for(int i = L; i <= R; i++)
v[e20+i] = {Z[i], i};
for(int i = e20-1; i >= 1; i--)
v[i] = max(v[2*i], v[2*i+1]);
// cerr << "build done\n";
}
pii rangemax(int L, int R)
{
// cerr << "range max called\n";
// cerr << L << ' ' << R << '\n';
L = e20+L;
R = e20+R+1;
pii res{-1, -1};
// pii lft_mx{-1, -1}, rgt_mx{-1, -1};
while(L < R)
{
if(L % 2 == 1)
{
res = max(res, v[L]);
L++;
}
if(R % 2 == 1)
{
R--;
res = max(res, v[R]);
}
L/=2;
R/=2;
// cerr << "!\n";
}
// cerr << "returning\n";
return res;
}
};
segtree ST;
vi subtree;
int build_tree(int l, int r)
{
if(r < l) return -1;
// cerr << "build tree " << l << ' ' << r << '\n';
// cerr << "build tree\n";
int m = ST.rangemax(l, r).second;
// cerr << "m = " << m << '\n';
// cerr << "m = " << m << '\n';
// cerr << lc[m] << ' ' << rc[m] << '\n';
lc[m] = build_tree(l, m-1);
rc[m] = build_tree(m+1, r);
if(lc[m] != -1) subtree[m] += subtree[lc[m]];
if(rc[m] != -1) subtree[m] += subtree[rc[m]];
// cerr << "build tree " << l << ' ' << r << " done\n";
return m;
}
vector<int> x1, x2;
vector<ll> y1, y2;
// struct seg
// {
// int i;
// };
int seg_ct = -1;
int new_segment(int X1, ll Y1, int X2, ll Y2)
{
seg_ct++;
x1.push_back(X1);
y1.push_back(Y1);
x2.push_back(X2);
y2.push_back(Y2);
// x1[seg_ct] = X1;
// y1[seg_ct] = Y1;
// x2[seg_ct] = X2;
// y2[seg_ct] = Y2;
return seg_ct;
}
ll get_slope(int i)
{
if(x2[i] == x1[i]) return 0;
else return (y2[i]-y1[i])/(x2[i]-x1[i]);
}
struct func
{
ll lp = 0;
deque<int> d;
void inc(ll W)
{
lp += W;
}
void push_back(func& K)
{
for(int k: K.d)
{
y1[k] += K.lp - lp;
y2[k] += K.lp - lp;
d.push_back(k);
// d.push_back(seg{k.x1, k.y1 + K.lp - lp, k.x2, k.y2 + K.lp - lp});
}
}
void push_front(func& K)
{
while(!K.d.empty())
{
int k = K.d.back();
y1[k] += K.lp - lp;
y2[k] += K.lp - lp;
d.push_front(k);
K.d.pop_back();
}
}
void front_AP(ll a, ll sl)
{
int xf = x1[d.front()];
int xb = -1;
while(!d.empty())
{
ll dy2 = y2[d.front()] + lp;
int dx2 = x2[d.front()];
ll dy1 = y1[d.front()] + lp;
int dx1 = x1[d.front()];
ll new_y2 = a + sl*(dx2 - xf);
if(new_y2 > dy2) break;
else if(a > dy1) break;
else
{
xb = max(xb, x2[d.front()]);
d.pop_front();
}
}
if(!d.empty())
{
// cerr << "case X\n";
ll dy1 = y1[d.front()] + lp;
ll dx1 = x1[d.front()];
ll new_y1 = a + sl*(dx1 - xf);
if(new_y1 <= y1[d[0]] + lp)
{
// ll d_sl = (d[0].y2 - d[0].y1)/(d[0].x2 - d[0].x1);
ll d_sl = get_slope(d[0]);
int lo = x1[d[0]];
int hi = x2[d[0]];
/*
find highest value of lo so that a + sl*(lo - xf) <= lp + y1[d[0]] + (lo - x1[d[0]])*d_sl
(sl - d_sl)*lo <= lp + y1[d[0]] - x1[d[0]]*d_sl + sl*xf
lo = (lp + y1[d[0]] - x1[d[0]]*d_sl + sl*xf)/(sl - d_sl)
*/
// while(lo != hi)
// {
// int mid = (lo+hi)/2 + 1;
// ll mid_y = lp + y1[d[0]]+ (mid-x1[d[0]])*d_sl;
//
// ll new_y = a + sl*(mid - xf);
//
// if(new_y <= mid_y)
// lo = mid;
// else
// hi = mid-1;
// }
if(sl == d_sl) lo = x1[d[0]];
else
{
lo = (lp + y1[d[0]] + (-x1[d[0]])*d_sl - a + sl*xf)/(sl - d_sl);
assert(sl >= d_sl);
}
xb = max(xb, lo);
x1[d[0]] = lo+1;
y1[d[0]] = y2[d[0]] - (x2[d[0]] - x1[d[0]])*d_sl;
}
}
if(xf <= xb)
{
d.push_front(new_segment(xf, a - lp, xb, a+sl*(xb-xf) - lp));
}
}
};
vector<func*> F(mx);
vector<func*> F2(mx);
void dfs(int u)
{
if(u == -1) return;
le[u] = re[u] = u;
if(lc[u] != -1)
{
dfs(lc[u]);
subtree[u] += subtree[lc[u]];
le[u] = le[lc[u]];
}
if(rc[u] != -1)
{
dfs(rc[u]);
subtree[u] += subtree[rc[u]];
re[u] = re[rc[u]];
}
for(int q: peak_queries[u])
{
int lo = 0;
int hi = sz(F[rc[u]]->d) - 1;
while(lo != hi)
{
int mid = (lo+hi)/2;
if(x2[F[rc[u]]->d[mid]] < R[q])
lo = mid+1;
else
hi = mid;
}
auto fr = F[rc[u]];
ll right_ans = fr->lp + y1[fr->d[lo]] + get_slope(fr->d[lo])*(R[q] - x1[fr->d[lo]]);
ans[q] = min(ans[q], ll(H[u])*(u - L[q] + 1) + right_ans);
}
ll left_ct = 1;
if(lc[u] != -1) left_ct += subtree[lc[u]];
if(rc[u] != -1)
{
F[rc[u]]->inc(ll(H[u])*(u - le[u] + 1));
}
ll dp_u;
if(lc[u] == -1)
{
dp_u = H[u];
}
else
{
dp_u = H[u] + y2[F[lc[u]]->d.back()] + F[lc[u]]->lp;
}
func ths;
ths.d.push_back(new_segment(u, dp_u, u, dp_u));
if(rc[u] != -1)
{
F[rc[u]]->front_AP(dp_u + H[u], H[u]);
}
if(lc[u] == -1 && rc[u] == -1)
{
F[u]->push_back(ths);
}
else if(lc[u] == -1)
{
F[u] = F[rc[u]];
F[u]->push_front(ths);
}
else if(rc[u] == -1)
{
F[u] = F[lc[u]];
F[u]->push_back(ths);
}
else
{
if(subtree[rc[u]] >= subtree[lc[u]])
{
F[u] = F[rc[u]];
F[u]->push_front(ths);
F[u]->push_front(*F[lc[u]]);
F[lc[u]]->d.clear();
}
else
{
F[u] = F[lc[u]];
F[u]->push_back(ths);
F[u]->push_back(*F[rc[u]]);
F[rc[u]]->d.clear();
}
}
// ths->d.clear();
ths.d.clear();
}
int rt;
vll minimum_costs(vi H_, vi L_, vi R_)
{
// for(int f: L_) cerr << "le = " << f << '\n';
//PART 1: PROCESS INPUT
H = H_;
L = L_;
R = R_;
H_.clear();
L_.clear();
R_.clear();
N = sz(H);
Q = sz(L);
// cerr << "queries: \n";
// for(int j = 0; j < Q; j++) cerr << L_[j] << ' ' << R_[j] << '\n';
//PART 2: DISCRETISE HEIGHTS
HD = vi(N);
vector<pii> P;
for(int i = 0; i < N; i++) P.push_back({H[i], i});
sort(P.begin(), P.end());
int ct = 0;
for(pii p:P)
{
ct++;
HD[p.second] = ct;
}
P.clear();
// for(int j = 0; j < Q; j++) cerr << j << " : " << M[j] << '\n';
ans = vll(Q, INF);
for(int t = 0; t <= 1; t++)
{
if(t == 1)
{
reverse(HD.begin(), HD.end());
reverse(H.begin(), H.end());
for(int j = 0; j < Q; j++)
{
L[j] = N-1 - L[j];
R[j] = N-1 - R[j];
swap(L[j], R[j]);
M[j] = N-1 - M[j];
}
}
for(int i = 0; i < N; i++)
{
peak_queries[i].clear();
}
// ST = segtree(0, N-1, HD);
if(t==0) ST.build_segtree(0, N-1, HD);
for(int j = 0; j < Q; j++)
{
if(t == 0)
M[j] = ST.rangemax(L[j], R[j]).second;
if(M[j] == R[j])
{
ans[j] = min(ans[j], ll(H[M[j]])*(R[j] - L[j] + 1));
}
else
peak_queries[M[j]].push_back(j);
// cerr << "j = " << j << ": " << M[j] << '\n';
}
// cerr << "done A\n";
le = vi(N, 1'000'000'000);
re = vi(N, -1);
if(t == 0)
{
// cerr << "entered\n";
subtree = vi(N, 1);
lc = rc = vi(N, -1);
rt = build_tree(0, N-1);
// cerr << "done B\n";
// cerr << "#\n";
}
else
{
// cerr << "entered t = " << 1 << '\n';
rt = N-1 - rt;
vi nwl(N), nwr(N);
for(int i = 0; i < N; i++)
{
if(lc[i] == -1) nwr[i] = -1;
else nwr[i] = N-1 - lc[i];
if(rc[i] == -1) nwl[i] = -1;
else nwl[i] = N-1 - rc[i];
}
reverse(subtree.begin(), subtree.end());
reverse(nwr.begin(), nwr.end());
rc = nwr;
reverse(nwl.begin(), nwl.end());
lc = nwl;
// cerr << "done t = 1\n";
}
// cerr << "\n\n\n\n\n T = " << t << '\n';
// for(int i = 0; i < N; i++) cerr << H[i] << ' ';
// cerr << "\n";
// for(int i = 0; i < N; i++) cerr << HD[i] << ' ';
// cerr << "\n";
// for(int i = 0; i < N; i++) cerr << lc[i] << ' ';
// cerr << "\n";
// for(int i = 0; i < N; i++) cerr << rc[i] << ' ';
// cerr << "\n";
// for(int i = 0; i < N; i++) cerr << subtree[i] << ' ';
// cerr << "\n";
// ST.clear_tree();
if(t == 0)
{
for(int i = 0; i < N; i++) F[i] = new func;
F2 = F;
}
else
{
F = F2;
for(int i = 0; i < N; i++)
{
F[i]->lp = 0;
F[i]->d.clear();
}
}
dfs(rt);
le.clear();
re.clear();
lc.clear();
rc.clear();
}
return ans;
}
