#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using ll = long long;
using vll = vector<ll>;
vll solve(vector<int> V, int delta, int len) {
stack<int> S;
vll re;
ll cur = 0;
for(int i = 0; i < len; ++i) {
while(!S.empty() && V[i + delta] > V[S.top() + delta]) {
int p = S.top();
S.pop();
int p2 = 0;
if(!S.empty()) p2 = S.top() + 1;
cur -= 1ll * (p - p2 + 1) * V[p + delta];
}
int p = 0;
if(!S.empty()) p = S.top() + 1;
cur += 1ll * (i - p + 1) * V[i + delta];
S.push(i);
re.push_back(cur);
}
return re;
}
using ii = pair<int, int>;
struct banda {
bool mono;
int len;
int vma = 0;
ii st, dr; /// perechi (val, len)
banda(int l = 0, int cul = 0) {
mono = 1;
len = l;
st = dr = {cul, l};
if(cul == 1) vma = l;
}
banda operator+(banda rhs) {
banda re;
if(mono && rhs.mono && st.first == rhs.st.first) {
re = banda(len + rhs.len, st.first);
return re;
}
re.vma = max(vma, rhs.vma);
re.st = st;
re.dr = rhs.dr;
if(mono && rhs.st.first == st.first) {
re.st.second += rhs.st.second;
}
if(dr.first == 1 && rhs.st.first == 1)
re.vma = max(re.vma, dr.second + rhs.st.second);
if(rhs.mono && dr.first == rhs.st.first)
re.dr.second += dr.second;
if(re.st.first == 1)
re.vma = max(re.vma, re.st.second);
if(re.dr.first == 1)
re.vma = max(re.vma, re.dr.second);
re.mono = 0;
return re;
}
};
struct AINT {
vector<banda> V;
int n;
AINT(int N) : n(N), V(4 * N) {}
void update(int u, int v) { update(u, v, 1, 0, n - 1); }
void update(int p, int v, int u, int s, int d) {
if(d < p || p < s) return;
if(s == d) {
V[u] = banda(1, v);
return;
}
update(p, v, u << 1, s, (s + d) >> 1);
update(p, v, u << 1 | 1, ((s + d) >> 1) + 1, d);
V[u] = V[u << 1] + V[u << 1 | 1];
}
banda query(int l, int r) { return query(l, r, 1, 0, n - 1); }
banda query(int l, int r, int u, int s, int d) {
int m = (s + d) >> 1;
if(l <= s && d <= r) return V[u];
if(r <= m) return query(l, r, u << 1, s, m);
if(m < l) return query(l, r, u << 1 | 1, m + 1, d);
return query(l, r, u << 1, s, m) + query(l, r, u << 1 | 1, m + 1, d);
}
};
vll minimum_costs(vi H, vi L, vi R) {
vector<int> S(H);
vi RH = H;
reverse(RH.begin(), RH.end());
vi RS(RH);
int n = H.size();
vll RE;
if(H.size() <= 5000 && L.size() <= 5000) {
for(int q = 0; q < L.size(); ++q) {
vll opt1 = solve(S, L[q], R[q] - L[q] + 1);
vll opt2 = solve(RS, n - 1 - R[q], R[q] - L[q] + 1);
reverse(opt2.begin(), opt2.end());
ll re = opt1[0] + opt2[0];
for(int i = 0; i < R[q] - L[q] + 1; i++)
re = min(re, opt1[i] + opt2[i] - H[i + L[q]]);
RE.push_back(re);
}
return RE;
}
///sper ca 0 sau 1;
AINT A(n);
for(int i = 0; i < n; ++i)
A.update(i, H[i]);
vll Re;
int q = L.size();
for(int i = 0; i < q; ++i) {
int v = A.query(L[i], R[i]).vma;
Re.push_back((R[i] - L[i] + 1) * 2 - v);
// cout << v << " ";
}
// cout << "\n\n";
return Re;
}
