#include <bits/stdc++.h>
#include "meetings.h"
using namespace std;
#define pb push_back
#define st first
#define nd second
typedef long long ll;
typedef long double ld;
const int II = 2'000'000'000;
const ll I = 1000LL * 1000LL * 1000LL * 1000LL * 1000LL * 1000LL;
const ll M = 1000LL * 1000LL * 1000LL + 7LL;
const int N = 1<<20;
int tab[N], ed[N][2], ran[N][2];
pair<int, int> rmq[N][20];
pair<int, int> que[N];
vector<int> wh[N];
ll answer[N];
pair<ll, ll> drz[2][2 * N];
ll lazd[2][2 * N];
int GetMax(int a, int b)
{
int d = b - a + 1;
int p = 31 - __builtin_clz(d);
if(rmq[a][p].st >= rmq[b - (1<<p) + 1][p].st)
return -rmq[a][p].nd;
return -rmq[b - (1<<p) + 1][p].nd;
}
void Licz(int n)
{
for(int i = n; i >= 1; --i)
{
rmq[i][0] = pair{tab[i], -i};
for(int j = 1; i + (1<<j) - 1 <= n; ++j)
rmq[i][j] = max(rmq[i][j - 1], rmq[i + (1<<(j - 1))][j - 1]);
}
vector<int> cur;
tab[0] = II; cur.pb(0);
for(int i = 1; i <= n; ++i)
{
while(tab[cur.back()] < tab[i])
{
ed[i][0] = cur.back();
cur.pop_back();
}
ed[cur.back()][1] = i;
cur.pb(i);
}
}
inline void Push(int r, int v)
{
for(int s = v * 2; s <= v * 2 + 1; ++s)
{
lazd[r][s] += lazd[r][v];
drz[r][s].nd += lazd[r][v];
}
lazd[r][v] = 0LL;
}
void Add(int r, int v, int p, int k, int pz, int kz, ll x)
{
if(pz > kz) return;
if(p > kz || k < pz) return;
if(p >= pz && k <= kz)
{
lazd[r][v] += x;
drz[r][v].nd += x;
return;
}
Add(r, v * 2, p, (p + k) / 2, pz, kz, x);
Add(r, v * 2 + 1, (p + k) / 2 + 1, k, pz, kz, x);
}
void Upd(int r, int v, int p, int k, pair<ll, ll> x)
{
if(v < N) Push(r, v);
if(x <= drz[r][v])
swap(x, drz[r][v]);
ll pos = (p + k) / 2;
if(x.st * pos + x.nd < drz[r][v].st * pos + drz[r][v].nd)
{
swap(drz[r][v], x);
if(v < N)
Upd(r, v * 2 + 1, (p + k) / 2 + 1, k, x);
}else
{
if(v < N)
Upd(r, v * 2, p, (p + k) / 2, x);
}
}
void Change(int r, int v, int p, int k, int pz, int kz, pair<ll, ll> x)
{
if(pz > kz) return;
if(p > kz || k < pz) return;
if(p >= pz && k <= kz)
{
Upd(r, v, p, k, x);
return;
}
Push(r, v);
Change(r, v * 2, p, (p + k) / 2, pz, kz, x);
Change(r, v * 2 + 1, (p + k) / 2 + 1, k, pz, kz, x);
}
ll Query(int r, int v)
{
ll pos = v;
v += N;
ll ans = I;
while(v > 0)
{
ans += lazd[r][v];
ans = min(ans, drz[r][v].st * pos + drz[r][v].nd);
v /= 2;
}
return ans;
}
void DFS(int v)
{
ran[v][0] = v; ran[v][1] = v;
for(int l = 0; l < 2; ++l)
if(ed[v][l] != 0)
{
DFS(ed[v][l]);
ran[v][l] = ran[ed[v][l]][l];
}
ll val = tab[v];
// cout << "\nDFS " << v << " | " << ed[v][0] << " " << ed[v][1] << '\n';
for(int l = 0; l < (int)wh[v].size(); ++l)
{
int a = que[wh[v][l]].st, b = que[wh[v][l]].nd;
ll cur = Query(1, a) + (ll)(b - v + 1) * val;
ll cur2 = Query(0, b) + (ll)(v - a + 1) * val;
// cout << "Q: " << wh[v][l] << " " << cur << " " << cur2 << "\n";
answer[wh[v][l]] = min(cur, cur2);
}
Add(0, 1, 0, N - 1, v, ran[v][1], val * (ll)(v - ran[v][0] + 1));
Add(1, 1, 0, N - 1, ran[v][0], v, val * (ll)(ran[v][1] - v + 1));
// cout << "XD: " << Query(1, 2) << "\n";
if(v > ran[v][0])
{
ll cur = Query(0, v - 1);
pair<ll, ll> a = pair{val, cur - (ll)(v - 1) * val};
Change(0, 1, 0, N - 1, v, ran[v][1], a);
}
if(v < ran[v][1])
{
ll cur = Query(1, v + 1);
pair<ll, ll> a = pair{-val, cur + (ll)(v + 1) * val};
Change(1, 1, 0, N - 1, ran[v][0], v, a);
}
// cout << "XD: " << Query(1, 2) << "\n";
}
vector<long long> minimum_costs(vector<int> H, vector<int> L, vector<int> R)
{
for(int r = 0; r < 2; ++r)
for(int i = 1; i < N; ++i)
drz[r][i] = pair{0LL, I};
int n = H.size(), q = L.size();
for(int i = 1; i <= n; ++i) tab[i] = H[i - 1];
Licz(n);
for(int i = 1; i <= q; ++i)
{
que[i] = pair{L[i - 1] + 1, R[i - 1] + 1};
int akt = GetMax(que[i].st, que[i].nd);
wh[akt].pb(i);
}
int s = GetMax(1, n);
DFS(s);
vector<ll> ans;
for(int i = 1; i <= q; ++i)
ans.pb(answer[i]);
return ans;
}
