#include "meetings.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define ll long long
#define ld long double
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define SZ(x) (int)(x).size()
template <typename T> using ord_set = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int n = 5003, n2 = 1e5 + 123;
int mx[n][n], h[n2];
ll p[n][n], s[n][n];
struct Node {
int l = 0, r = 0;
int ans = 0, P = 0, S = 0;
void clean() {
l = r = ans = P = S = 0;
}
};
Node merge(Node a, Node b) {
if (a.l == 0 && a.r == 0) return b;
Node c;
c.l = a.l, c.r = b.r;
c.P = a.P;
if (a.P == a.r - a.l + 1)
c.P += b.P;
c.S = b.S;
if (b.S == b.r - b.l + 1)
c.S += a.S;
c.ans = max({a.ans, b.ans, a.S + b.P});
return c;
}
Node t[(1 << 18) + 1];
void build(int v, int l, int r) {
t[v].l = l, t[v].r = r;
if (l == r) {
t[v].P = t[v].S = t[v].ans = (h[l - 1] == 1);
return;
}
int m = l + r >> 1;
build(v << 1, l, m);
build(v << 1 | 1, m + 1, r);
t[v] = merge(t[v << 1], t[v << 1 | 1]);
}
Node tmp;
void get(int v, int l, int r) {
if (t[v].l > r || t[v].r < l) return;
if (t[v].l >= l && t[v].r <= r) {
tmp = merge(tmp, t[v]);
return;
}
get(v << 1, l, r);
get(v << 1 | 1, l, r);
}
int getans(int l, int r) {
tmp.clean();
get(1, l, r);
return tmp.ans;
}
std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L,
std::vector<int> R) {
int Q = L.size();
std::vector<long long> C(Q);
int N = SZ(H);
for (int i = 0; i < N; i++) h[i] = H[i];
if (N <= 5000 && Q <= 5000) {
for (int i = 0; i < N; i++)
for (int j = i; j < N; j++)
mx[i][j] = (i == j) ? H[i] : max(mx[i][j - 1], H[j]);
for (int j = 0; j < N; j++)
for (int i = j; i >= 0; i--)
p[i][j] = (i == j) ? H[i] : (p[i + 1][j] + mx[i][j]);
for (int i = 0; i < N; i++)
for (int j = i; j < N; j++)
s[i][j] = (i == j) ? H[i] : (s[i][j - 1] + mx[i][j]);
for (int i = 0; i < Q; i++) {
int l = L[i], r = R[i];
ll res = 1e18;
for (int i = l; i <= r; i++)
res = min(res, p[l][i] + s[i][r] - H[i]);
C[i] = res;
}
} else {
build(1, 1, N);
for (int i = 0; i < Q; i++) {
int l = L[i], r = R[i];
l++, r++;
C[i] = 2 * (r - l + 1) - getans(l, r);
}
}
return C;
}
