#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 7.5e5 + 10;
int n, q;
ll h[maxn];
/// Cartesian tree data
int left_child[maxn], right_child[maxn];
int left_border[maxn], right_border[maxn];
int root, depth[maxn];
void cartesian_tree()
{
stack < int > lf;
for (int i = 1; i <= n; i ++)
{
left_child[i] = -1;
while(!lf.empty() && h[lf.top()] <= h[i])
{
left_child[i] = lf.top();
lf.pop();
}
if (lf.empty())
left_border[i] = 1;
else
left_border[i] = lf.top() + 1;
lf.push(i);
}
stack < int > rf;
for (int i = n; i >= 1; i --)
{
right_child[i] = -1;
while(!rf.empty() && h[rf.top()] < h[i])
{
right_child[i] = rf.top();
rf.pop();
}
if (rf.empty())
right_border[i] = n;
else
right_border[i] = rf.top() - 1;
rf.push(i);
}
for (int i = 1; i <= n; i ++)
{
if (left_border[i] == 1 && right_border[i] == n)
{
root = i;
break;
}
}
}
void calc_depth(int ver)
{
//cout << "vertex " << ver << endl;
//cout << "left border " << left_border[ver] << " right border " << right_border[ver] << endl;
if (left_child[ver] != -1)
{
depth[left_child[ver]] = depth[ver] + 1;
calc_depth(left_child[ver]);
}
if (right_child[ver] != -1)
{
depth[right_child[ver]] = depth[ver] + 1;
calc_depth(right_child[ver]);
}
}
struct query
{
int l, r, idx;
query(int _l = 0, int _r = 0, int _idx = 0)
{
l = _l;
r = _r;
idx = _idx;
}
};
query task[maxn];
vector < query > spot[maxn];
struct line
{
ll k, m;
line (ll _k = 0, ll _m = 0)
{
k = _k;
m = _m;
}
ll get(ll x)
{
return k * x + m;
}
};
void assign_queries()
{
for (int i = 1; i <= q; i ++)
{
int mx = -1;
for (int j = task[i].l; j <= task[i].r; j ++)
{
if (mx == -1 || depth[j] < depth[mx])
mx = j;
}
spot[mx].push_back(task[i]);
}
}
const ll inf = 1e18;
ll left_price[maxn], right_price[maxn];
ll answer[maxn];
void chmin(ll &var, ll val)
{
var = min(var, val);
}
void conquer(int root)
{
line left_line(h[root], - (root - 1) * h[root]), right_line(- h[root], + (root + 1) * h[root]);
if (root != left_border[root])
left_line.m += left_price[root - 1];
if (root != right_border[root])
right_line.m += right_price[root + 1];
if (root == left_border[root])
left_price[root] = h[root];
else
left_price[root] = left_price[root - 1] + h[root];
for (int pivot = root + 1; pivot <= right_border[root]; pivot ++)
{
left_price[pivot] += (root - left_border[root] + 1) * h[root];
chmin(left_price[pivot], left_line.get(pivot));
}
if (root == right_border[root])
right_price[root] = h[root];
else
right_price[root] = right_price[root + 1] + h[root];
for (int pivot = root - 1; pivot >= left_border[root]; pivot --)
{
right_price[pivot] += (right_border[root] - root + 1) * h[root];
chmin(right_price[pivot], right_line.get(pivot));
}
}
void divide(int root)
{
if (left_child[root] != -1)
divide(left_child[root]);
if (right_child[root] != -1)
divide(right_child[root]);
for (query cur : spot[root])
{
///cout << "answer " << left_border[root] << " " << right_border[root] << " " << cur.idx << endl;
ll left_opt = right_price[cur.l] + (ll)(cur.r - root + 1) * h[root];
ll right_opt = (ll)(root - cur.l + 1) * h[root] + left_price[cur.r];
chmin(answer[cur.idx], min(left_opt, right_opt));
}
conquer(root);
/**cout << "range " << left_border[root] << " " << right_border[root] << endl;
for (int i = left_border[root]; i <= right_border[root]; i ++ )
cout << left_price[i] << " ";
cout << endl;
for (int i = left_border[root]; i <= right_border[root]; i ++ )
cout << right_price[i] << " ";
cout << endl;*/
}
vector < ll > get_result()
{
vector < ll > res;
for (int i = 1; i <= q; i ++)
res.push_back(answer[i]);
return res;
}
vector<long long> minimum_costs(vector<int> H, vector<int> L,
vector<int> R)
{
n = H.size();
q = L.size();
for (int i = 1; i <= n; i ++)
{
h[i] = H[i - 1];
}
for (int i = 1; i <= q; i ++)
{
task[i] = query(L[i - 1] + 1, R[i - 1] + 1, i);
answer[i] = inf;
}
cartesian_tree();
calc_depth(root);
assign_queries();
divide(root);
vector < ll > res = get_result();
return res;
}
