#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];
ll calc(int pivot, int left, int right)
{
ll mx = 0, ans = 0;
for (int i = pivot; i >= left; i --)
{
mx = max(mx, h[i]);
ans += mx;
}
mx = h[pivot];
for (int i = pivot + 1; i <= right; i ++)
{
mx = max(mx, h[i]);
ans += mx;
}
return ans;
}
ll pref[maxn], suff[maxn];
ll query(int left, int right)
{
ll ans = 1e18;
/**for (int pivot = left; pivot <= right; pivot ++)
{
ll cur = calc(pivot, left, right);
cout << cur << " ";
ans = min(ans, calc(pivot, left, right));
}
cout << endl;*/
stack < int > st;
ll sum = 0;
for (int i = left; i <= right; i ++)
{
while(!st.empty() && h[st.top()] < h[i])
{
int val = st.top();
st.pop();
int bef = left - 1;
if (!st.empty())
bef = st.top();
sum = sum - (ll)(val - bef) * h[val];
}
int bef = left - 1;
if (!st.empty())
{
bef = st.top();
}
sum = sum + (ll)(i - bef) * h[i];
st.push(i);
pref[i] = sum;
///cout << pref[i] << " ";
}
///cout << endl;
while(!st.empty())
st.pop();
sum = 0;
for (int i = right; i >= left; i --)
{
while(!st.empty() && h[st.top()] < h[i])
{
int val = st.top();
st.pop();
int aft = right + 1;
if (!st.empty())
aft = st.top();
sum = sum - (ll)(aft - val) * h[val];
}
int aft = right + 1;
if (!st.empty())
{
aft = st.top();
}
sum = sum + (ll)(aft - i) * h[i];
st.push(i);
suff[i] = sum;
}
for (int i = left; i <= right; i ++)
{
ans = min(ans, pref[i] + suff[i] - h[i]);
}
return ans;
}
struct node
{
int lf, rf, sz, mx;
node(int _lf = 0, int _rf = 0, int _sz = 0, int _mx = 0)
{
lf = _lf;
rf = _rf;
sz = _sz;
mx = _mx;
}
};
node merge_node(node l, node r)
{
node m;
m.mx = max(max(l.mx, r.mx), l.rf + r.lf);
m.lf = l.lf;
if (l.lf == l.sz)
m.lf = l.lf + r.lf;
m.rf = r.rf;
if (r.rf == r.sz)
m.rf = r.rf + l.rf;
m.sz = l.sz + r.sz;
return m;
}
node tree[4 * maxn];
void build(int root, int left, int right)
{
if (left == right)
{
if (h[left] == 1)
{
tree[root] = node(1, 1, 1, 1);
}
else
{
tree[root] = node(0, 0, 1, 0);
}
return;
}
int mid = (left + right) / 2;
build(root * 2, left, mid);
build(root * 2 + 1, mid + 1, right);
tree[root] = merge_node(tree[root * 2], tree[root * 2 + 1]);
}
node query_range(int root, int left, int right, int qleft, int qright)
{
if (left > qright || right < qleft)
return node();
if (left >= qleft && right <= qright)
return tree[root];
int mid = (left + right) / 2;
return merge_node(query_range(root * 2, left, mid, qleft, qright),
query_range(root * 2 + 1, mid + 1, right, qleft, qright));
}
vector<long long> minimum_costs(vector<int> H, vector<int> L,
vector<int> R)
{
n = H.size();
q = L.size();
for (int i = 0; i < n; i ++)
{
h[i] = H[i];
}
vector < ll > res(q);
build(1, 0, n - 1);
for (int i = 0; i < q; i ++)
{
if (n <= 5000 && q <= 5000)
res[i] = query(L[i], R[i]);
else
{
node cur = query_range(1, 0, n - 1, L[i], R[i]);
ll ans = (R[i] - L[i] + 1) * 2 - cur.mx;
res[i] = ans;
}
}
return res;
}
