#include <bits/stdc++.h>
#include "meetings.h"
using namespace std;
typedef long long ll;
struct Node {
ll left, right, total;
bool full;
};
vector<ll> minimum_costs(vector<int> h, vector<int> l, vector<int> r) {
ll n = h.size(), q = l.size();
vector<ll> res;
if (n <= 5000 && q <= 5000) {
vector<vector<ll>> lut(n, vector<ll>(n));
for (int c = 0; c < n; c++) {
ll sum = 0;
int mx = h[c];
for (int i = c - 1; i >= 0; i--) {
mx = max(mx, h[i]);
sum += mx;
lut[c][i] = sum;
}
sum = 0;
mx = h[c];
for (int i = c + 1; i < n; i++) {
mx = max(mx, h[i]);
sum += mx;
lut[c][i] = sum;
}
}
for (int q1 = 0; q1 < q; q1++) {
ll mn = 1ll << 62ll;
for (int c = l[q1]; c <= r[q1]; c++) {
ll val = h[c] + lut[c][l[q1]] + lut[c][r[q1]];
mn = min(mn, val);
}
res.push_back(mn);
}
return res;
}
res.resize(q);
ll pow2 = 1 << (int)ceil(log2(n));
vector<Node> seg(2 * pow2);
for (int i = 0; i < n; i++) {
seg[pow2 + i].left = seg[pow2 + i].right = seg[pow2 + i].total = seg[pow2 + i].full = h[i] & 1;
}
for (int i = pow2 - 1; i > 0; i--) {
seg[i].left = seg[2*i].left;
seg[i].right = seg[2*i+1].right;
if (seg[2*i].full) seg[i].left += seg[2*i+1].left;
if (seg[2*i+1].full) seg[i].right += seg[2*i].right;
seg[i].total = max({seg[i].left, seg[i].right, seg[2*i].total, seg[2*i+1].total, seg[2*i].right + seg[2*i+1].left});
seg[i].full = seg[2*i].full && seg[2*i+1].full;
}
while (q--) {
res[q] = 2 * (r[q] - l[q] + 1);
int low = pow2 + l[q], high = pow2 + r[q];
Node nd;
nd.left = nd.right = 0;
ll mx = 0;
while (low <= high) {
if (low & 1) {
mx = max(mx, seg[low].total);
mx = max(mx, nd.left + seg[low].left);
if (seg[low].full) {
nd.left += seg[low].right;
}
else {
nd.left = seg[low].right;
}
low++;
}
if (!(high & 1)) {
mx = max(mx, seg[high].total);
mx = max(mx, nd.right + seg[high].right);
if (seg[high].full) {
nd.right += seg[high].left;
}
else {
nd.right = seg[high].left;
}
high--;
}
low >>= 1; high >>= 1;
}
mx = max(mx, nd.left + nd.right);
res[q] -= mx;
}
return res;
}
