#include <bits/stdc++.h>
#include "meetings.h"
using namespace std;
using ll = long long;
struct node {
int pref = 0, suf = 0, ans = 0, sz = 0;
node() = default;
node(int a) {
if (a == 1) {
pref = suf = ans = 1;
}
sz = 1;
}
};
node operator+(node a, node b) {
node res;
res.sz = a.sz + b.sz;
res.pref = (a.pref == a.sz ? a.sz + b.pref : a.pref);
res.suf = (b.suf == b.sz ? b.sz + a.suf : b.suf);
res.ans = max({res.pref, res.suf, a.ans, b.ans, a.suf + b.pref});
return res;
}
vector<node> tree;
int sz = 1;
void init(vector<int> &a) {
int n = (int)a.size();
sz = 1;
while (sz < n) {
sz <<= 1;
}
tree.assign(sz << 1, {});
for (int i = 0; i < n; ++i) {
tree[i + sz] = node(a[i]);
}
for (int i = sz - 1; i > 0; --i) {
tree[i] = tree[i << 1] + tree[i << 1 | 1];
}
}
node get(int l, int r, int x = 1, int lx = 0, int rx = sz) {
if (l >= rx || lx >= r) return {};
if (l <= lx && rx <= r) {
return tree[x];
}
int mid = (lx + rx) >> 1;
return get(l, r, x << 1, lx, mid) + get(l, r, x << 1 | 1, mid, rx);
}
vector<ll> minimum_costs(vector<int> a, vector<int> L, vector<int> R) {
int n = (int) a.size();
int q = (int) L.size();
vector<ll> ans(q, LLONG_MAX);
if (*max_element(a.begin(), a.end()) <= 2) {
init(a);
for (int i = 0; i < q; ++i) {
ans[i] = (R[i] - L[i] + 1) * 2 - get(L[i], R[i] + 1).ans;
}
return ans;
} else {
vector<ll> pref(n), suf(n);
for (int t = 0; t < q; ++t) {
int l = L[t], r = R[t];
vector<int> stk;
ll sum = 0;
for (int i = l; i <= r; ++i) {
while (!stk.empty() && a[stk.back()] <= a[i]) {
int j = stk.back();
stk.pop_back();
sum += (a[i] - a[j]) * (ll) (j - (stk.empty() ? l - 1 : stk.back()));
}
stk.push_back(i);
sum += a[i];
pref[i] = sum;
}
stk.clear();
sum = 0;
for (int i = r; i >= l; --i) {
while (!stk.empty() && a[stk.back()] <= a[i]) {
int j = stk.back();
stk.pop_back();
sum += (a[i] - a[j]) * (ll) ((stk.empty() ? r + 1 : stk.back()) - j);
}
stk.push_back(i);
sum += a[i];
suf[i] = sum;
}
ans[t] = LLONG_MAX;
for (int i = l; i <= r; ++i) {
ans[t] = min(ans[t], pref[i] + suf[i] - a[i]);
}
}
return ans;
}
}
