#include <bits/stdc++.h>
#include "meetings.h"
/// #pragma GCC optimize ("Ofast")
/// #pragma GCC target ("avx2")
/// #pragma GCC optimize("unroll-loops")
using namespace std;
using ll = long long;
using ld = long double;
using ii = pair<ll, ll>;
using vi = vector<int>;
#define ff first
#define ss second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define lb lower_bound
const int MOD = 1e9 + 7;
ll N, Q, DP[5005][5005], SP[100001][20], LOG[100001];
ll A[100005];
struct node{
int val, p, s, r;
} ST[400005];
ll query(int i, int j) {
int K = LOG[j - i + 1];
return max(SP[i][K], SP[j - (1 << K) + 1][K]);
}
node merge(node U, node V) {
node res;
res.p = U.p, res.s = V.s;
if(U.r) res.p = U.val + V.p;
if(V.r) res.s = U.s + V.val;
res.val = max({U.val, V.val, U.s + V.p});
res.r = (U.r & V.r);
return res;
}
void build(int v, int l, int r) {
if(l == r) {
int x = (A[l] == 1);
ST[v] = {x, x, x, x};
return;
}
build(v * 2, l, (l + r) / 2);
build(v * 2 + 1, (l + r) / 2 + 1, r);
ST[v] = merge(ST[v * 2], ST[v * 2 + 1]);
}
node query(int v, int l, int r, int lo, int hi) {
if(l > hi || r < lo) return {-1, -1, -1, -1};
if(l >= lo && r <= hi) return ST[v];
node X = query(v * 2, l, (l + r) / 2, lo, hi);
node Y = query(v * 2 + 1, (l + r) / 2 + 1, r, lo, hi);
if(X.val == -1) return Y;
if(Y.val == -1) return X;
return merge(X, Y);
}
vector<ll> subtask(vector<int> H, vector<int> L, vector<int> R) {
for(int l = 0; l < N; l++)
A[l] = H[l];
build(1, 0, N - 1);
vector<ll> res(Q, -1);
for(int l = 0; l < Q; l++) {
int X = L[l], Y = R[l];
ll best = query(1, 0, N - 1, X, Y).val;
res[l] = best + (Y - X + 1) * 2;
}
return res;
}
vector<ll> minimum_costs(vector<int> H, vector<int> L, vector<int> R) {
int M = 0; LOG[1] = 0; N = H.size(), Q = L.size();
for(int l = 0; l < N; l++)
M = max(M, H[l]);
if(M <= 2) return subtask(H, L, R);
for(int l = 2; l <= N; l++)
LOG[l] = LOG[l / 2] + 1;
for(int l = 0; l < N; l++)
SP[l][0] = H[l];
for(int l = 1; l < 20; l++)
for(int i = 0; i + (1 << l) <= N; i++)
SP[i][l] = max(SP[i][l - 1], SP[i + (1 << (l - 1))][l - 1]);
for(int l = 0; l < N; l++) {
DP[l][l] = H[l];
for(int i = l + 1; i < N; i++) {
DP[l][i] = DP[l][i - 1];
DP[l][i] += query(l, i);
}
for(int i = l - 1; i >= 0; i--) {
DP[l][i] = DP[l][i + 1];
DP[l][i] += query(i, l);
}
}
vector<ll> res(Q, -1);
for(int l = 0; l < Q; l++) {
ll best = 1000000000LL * 1LL * 1000000000LL;
for(int i = L[l]; i <= R[l]; i++) {
ll A = DP[i][R[l]];
if(i != L[l]) A += DP[i][L[l]] - H[i];
best = min(best, A);
}
res[l] = best;
}
return res;
}
