#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ari2 = array<int, 2>;
#define vt vector
#define size(x) (int((x).size()))
#define all(x) begin(x), end(x)
#define REP(a, b, c, d) for (int a = (b); (d) > 0 ? a <= (c) : a >= (c); a += (d))
#define FOR(a, b, c) REP(a, b, c, 1)
#define ROF(a, b, c) REP(a, b, c, -1)
vt<ll> Sub2(vt<int> H, vt<int> L, vt<int> R) {
const int N = size(H), Q = size(L);
vt<ll> ans(Q, LLONG_MAX);
ll fdp[N], rdp[N];
FOR(q, 0, Q-1) {
int l = L[q], r = R[q];
vt<int> sk;
FOR(i, l, r) {
while (size(sk) && H[sk.back()] <= H[i])
sk.pop_back();
fdp[i] = (size(sk) ? fdp[sk.back()] : 0ll) + 1ll * H[i] * (i - (size(sk) ? sk.back() : l-1));
sk.push_back(i);
}
sk.clear();
ROF(i, r, l) {
while (size(sk) && H[sk.back()] <= H[i])
sk.pop_back();
rdp[i] = (size(sk) ? rdp[sk.back()] : 0ll) + 1ll * H[i] * ((size(sk) ? sk.back() : r+1) - i);
ans[q] = min(ans[q], rdp[i] + fdp[i] - H[i]);
sk.push_back(i);
}
}
return ans;
}
struct ST {
struct Node {
int ans, p, s, len;
};
vt<Node> st;
ST(vt<int> &A) {
st.resize(size(A) << 2);
build(A);
}
Node merge(Node a, Node b) {
return {max({a.ans, b.ans, a.s + b.p}), a.p + (a.p == a.len) * b.p, b.s + (b.s == b.len) * a.s, a.len + b.len};
}
#define lc i << 1
#define rc i << 1 | 1
void build(vt<int> &A, int i = 1, int tl = 0, int tr = -1) {
if (tr < 0)
tr += size(st) >> 2;
if (tl == tr)
st[i] = {A[tl] < 2, A[tl] < 2, A[tl] < 2, 1};
else {
int tm = tl + tr >> 1;
build(A, lc, tl, tm);
build(A, rc, tm+1, tr);
st[i] = merge(st[lc], st[rc]);
}
}
Node qry(int ql, int qr, int i = 1, int tl = 0, int tr = -1) {
if (tr < 0)
tr += size(st) >> 2;
if (ql <= tl && tr <= qr)
return st[i];
if (tl > qr || tr < ql)
return {0, 0, 0, 0};
int tm = tl + tr >> 1;
return merge(qry(ql, qr, lc, tl, tm), qry(ql, qr, rc, tm+1, tr));
}
#undef lc
#undef rc
};
vt<ll> Sub3(vt<int> H, vt<int> L, vt<int> R) {
const int Q = size(L);
ST st(H);
vt<ll> ans(Q);
FOR(i, 0, Q-1) {
int l = L[i], r = R[i];
int v = st.qry(l, r).ans;
ans[i] = v + 2 * (r - l + 1 - v);
}
return ans;
}
vt<ll> minimum_costs(vt<int> H, vt<int> L, vt<int> R) {
const int N = size(H), Q = size(L);
if (N <= 5000 && Q <= 5000)
return Sub2(H, L, R);
if (*max_element(all(H)) < 3)
return Sub3(H, L, R);
}
