#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
#define m_p make_pair
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
typedef long long ll;
const int N = 100005;
int n, qq;
vector<ll> solv2(vector<int> H, vector<int> L, vector<int> R)
{
vector<ll> v;
for (int ii = 0; ii < qq; ++ii)
{
int l = L[ii];
int r = R[ii];
vector<ll> ans(n);
for (int i = l; i <= r; ++i)
ans[i] = 0;
stack<pair<int, int> > s;
ll yans = 0;
for (int i = l; i <= r; ++i)
{
int q = 1;
while (!s.empty() && H[i] >= s.top().fi)
{
yans -= s.top().fi * 1LL * s.top().se;
q += s.top().se;
s.pop();
}
s.push(m_p(H[i], q));
yans += s.top().fi * 1LL * s.top().se;
ans[i] += yans;
}
while (!s.empty())
s.pop();
yans = 0;
for (int i = r; i >= l; --i)
{
int q = 1;
while (!s.empty() && H[i] >= s.top().fi)
{
yans -= s.top().fi * 1LL * s.top().se;
q += s.top().se;
s.pop();
}
s.push(m_p(H[i], q));
yans += s.top().fi * 1LL * s.top().se;
ans[i] += yans - H[i];
}
yans = ans[l];
for (int i = l; i <= r; ++i)
yans = min(yans, ans[i]);
v.push_back(yans);
}
return v;
}
struct ban
{
int l, r, ans;
int q;
ban()
{
ans = l = r = 0;
q = 0;
}
ban(int x)
{
if (x == 1)
{
ans = l = r = 1;
}
else
{
ans = l = r = 0;
}
q = 1;
}
};
ban t[N * 4];
ban mer(const ban& l, const ban& r)
{
ban res;
if (l.q == l.l)
res.l = l.q + r.l;
else
res.l = l.l;
if (r.q == r.r)
res.r = r.q + l.r;
else
res.r = r.r;
res.ans = max(l.ans, r.ans);
res.ans = max(res.ans, l.r + r.l);
res.q = l.q + r.q;
return res;
}
void bil(const vector<int>& H, int tl, int tr, int pos)
{
if (tl == tr)
{
t[pos] = ban(H[tl]);
return;
}
int m = (tl + tr) / 2;
bil(H, tl, m, pos * 2);
bil(H, m + 1, tr, pos * 2 + 1);
t[pos] = mer(t[pos * 2], t[pos * 2 + 1]);
}
ban qry(int tl, int tr, int l, int r, int pos)
{
if (l > r)
return ban();
if (tl == l && tr == r)
return t[pos];
int m = (tl + tr) / 2;
return mer(qry(tl, m, l, min(m, r), pos * 2),
qry(m + 1, tr, max(m + 1, l), r, pos * 2 + 1));
}
vector<ll> solv3(vector<int> H, vector<int> L, vector<int> R)
{
bil(H, 0, n - 1, 1);
vector<ll> v;
for (int ii = 0; ii < qq; ++ii)
{
int l = L[ii];
int r = R[ii];
ban u = qry(0, n - 1, l, r, 1);
v.push_back(u.ans + (r - l + 1 - u.ans) * 2);
}
return v;
}
std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L,
std::vector<int> R)
{
n = sz(H);
qq = sz(L);
if (n <= 5000 && qq <= 5000)
return solv2(H, L, R);
return solv3(H, L, R);
}
