#include <bits/stdc++.h>
using namespace std;
using i32 = int;
using i64 = long long;
template <typename T>
using V = vector<T>;
template <typename T>
using VV = V<V<T>>;
#define OVERRIDE4(a, b, c, d, ...) d
#define REP2(i, n) for (i32 i = 0; i < (i32)(n); ++i)
#define REP3(i, l, r) for (i32 i = (i32)(l); i < (i32)(r); ++i)
#define PER2(i, n) for (i32 i = (i32)(n) - 1; i >= 0; --i)
#define PER3(i, l, r) for (i32 i = (i32)(r) - 1; i >= (i32)(l); --i)
#define REP(...) OVERRIDE4(__VA_ARGS__, REP3, REP2)(__VA_ARGS__)
#define PER(...) OVERRIDE4(__VA_ARGS__, PER3, PER2)(__VA_ARGS__)
#define LEN(x) (i32)size(x)
#define ALL(x) begin(x), end(x)
template <typename T>
bool chmin(T &x, const T &y) {
if (x > y) {
x = y;
return true;
}
return false;
}
template <typename T>
bool chmax(T &x, const T &y) {
if (x < y) {
x = y;
return true;
}
return false;
}
#include "meetings.h"
constexpr i32 INF = 1001001001;
constexpr i64 INF64 = 3003003003003003003;
i64 solve_naive(V<i32> h) {
i32 n = LEN(h);
V<i64> cost(n, 0);
V<pair<i64, i32>> stc;
stc.emplace_back(INF, -1);
i64 cur = 0;
REP(i, n) {
while (stc.back().first <= h[i]) {
i64 v;
i32 j;
tie(v, j) = stc.back();
stc.pop_back();
cur -= v * (j - stc.back().second);
}
cur += (i64)h[i] * (i - stc.back().second);
stc.emplace_back(h[i], i);
cost[i] += cur;
}
stc.clear();
stc.emplace_back(INF, n);
cur = 0;
PER(i, n) {
while (stc.back().first <= h[i]) {
i64 v;
i32 j;
tie(v, j) = stc.back();
stc.pop_back();
cur -= v * (stc.back().second - j);
}
cur += (i64)h[i] * (stc.back().second - i);
stc.emplace_back(h[i], i);
cost[i] += cur;
}
REP(i, n) {
cost[i] -= h[i];
}
i64 mn = INF64;
REP(i, n) {
chmin(mn, cost[i]);
}
return mn;
}
struct Data {
i32 len, l1, r1, m1;
};
Data id() {
return Data{0, 0, 0, 0};
}
Data op(Data x, Data y) {
i32 len = x.len + y.len;
i32 l1 = (x.len == x.l1 ? x.len + y.l1 : x.l1);
i32 r1 = (y.len == y.r1 ? x.r1 + y.len : y.r1);
i32 m1 = max({x.m1, y.m1, x.r1 + y.l1});
return Data{len, l1, r1, m1};
}
i32 ceil_pow2(i32 n) {
i32 k = 1;
while (k < n) {
k *= 2;
}
return k;
}
class Segtree {
i32 n;
V<Data> dat;
public:
Segtree(i32 _n) : n(ceil_pow2(_n)), dat(2 * n, id()) {}
void update(i32 idx, Data d) {
idx += n;
dat[idx] = d;
idx /= 2;
while (idx > 0) {
dat[idx] = op(dat[2 * idx], dat[2 * idx + 1]);
idx /= 2;
}
}
Data prod(i32 l, i32 r) const {
l += n;
r += n;
Data lp = id(), rp = id();
while (l < r) {
if (l & 1) {
lp = op(lp, dat[l++]);
}
if (r & 1) {
rp = op(dat[--r], rp);
}
l /= 2;
r /= 2;
}
return op(lp, rp);
}
};
V<i64> minimum_costs(V<i32> _h, V<i32> l, V<i32> r) {
i32 n = LEN(_h);
i32 q = LEN(l);
V<i64> h(n);
REP(i, n) {
h[i] = _h[i];
}
REP(i, q) {
++r[i];
}
REP(i, n) {
assert(h[i] <= 2);
}
Segtree seg(n);
REP(i, n) {
seg.update(i, h[i] == 1 ? Data{1, 1, 1, 1} : Data{1, 0, 0, 0});
}
V<i64> ret(q);
REP(i, q) {
ret[i] = 2 * (r[i] - l[i]);
ret[i] -= seg.prod(l[i], r[i]).m1;
}
return ret;
}
