// Ignut
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = 1e18 + 123;
const int MAXN = 1e5 + 123;
// "1" segments
vector<pair<int, int>> vec;
int sz;
// maximum segment tree
int t[4 * MAXN];
void Build(int v, int l, int r) {
if (l == r) {
t[v] = vec[l].second - vec[l].first + 1;
return;
}
int mid = l + (r - l) / 2;
Build(v * 2, l, mid), Build(v * 2 + 1, mid + 1, r);
t[v] = max(t[v * 2], t[v * 2 + 1]);
}
int Max(int v, int l, int r, int ql, int qr) {
if (l > qr || ql > r)
return 0;
if (l >= ql && r <= qr)
return t[v];
int mid = l + (r - l) / 2;
return max(Max(v * 2, l, mid, ql, qr), Max(v * 2 + 1, mid + 1, r, ql, qr));
}
vector<ll> minimum_costs(vector<int> H, vector<int> L, vector<int> R) {
int N = H.size();
int Q = L.size();
if (N <= 5555 && Q <= 5555) {
ll goLeft[N][N] = {};
ll goRight[N][N] = {};
for (int i = 0; i < N; i ++) {
ll mx = H[i];
ll sum = 0;
for (int j = i; j >= 0; j --) {
mx = max(mx, 1ll * H[j]);
sum += mx;
goLeft[i][j] = sum;
}
mx = H[i];
sum = 0;
for (int j = i; j < N; j ++) {
mx = max(mx, 1ll * H[j]);
sum += mx;
goRight[i][j] = sum;
}
}
vector<ll> res;
for (int i = 0; i < Q; i ++) {
ll ans = INF;
for (int s = L[i]; s <= R[i]; s ++)
ans = min(ans, goLeft[s][L[i]] + goRight[s][R[i]] - H[s]);
res.push_back(ans);
}
return res;
}
vec.clear();
int l = -1;
for (int i = 0; i < N; i ++) {
if (H[i] == 1) {
if (l == -1) l = i;
}
else {
if (l != -1) vec.push_back({l, i - 1});
l = -1;
}
}
if (l != -1) vec.push_back({l, N - 1});
sz = vec.size();
Build(1, 0, sz - 1);
vector<ll> res;
for (int i = 0; i < Q; i ++) {
int l = L[i], r = R[i];
int il = lower_bound(vec.begin(), vec.end(), make_pair(l, -1)) - vec.begin();
int ir = upper_bound(vec.begin(), vec.end(), make_pair(r, N + 1)) - vec.begin();
if (il == ir) {
// cout << "I\n";
res.push_back((r - l + 1) * 2);
continue;
}
int maxCnt = min(r, vec[il].second) - max(l, vec[il].first) + 1;
if (il + 1 == ir) {
// cout << "II\n";
res.push_back((r - l + 1) * 2 - maxCnt);
continue;
}
// cout << "III\n";
maxCnt = max(maxCnt, Max(1, 0, sz - 1, il + 1, ir - 1));
res.push_back((r - l + 1) * 2 - maxCnt);
}
return res;
}
