#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 5555;
const int maxnn = 1111111;
const int INF = 1000000007;
long long pref[maxn][maxn];
long long MAX[maxn][maxn];
struct node{
long long seg;
long long prf;
long long sff;
long long sum;
};
node combine(node a, node b){
node c;
c.seg = max(a.sff + b.prf, max(a.seg, b.seg));
c.prf = max(a.prf, a.sum + b.prf);
c.sff = max(b.sff, b.sum + a.sff);
c.sum = a.sum + b.sum;
return c;
}
int a[maxnn];
node t[maxnn];
void build(int v, int tl, int tr){
if (tl == tr) {
node ttt;
ttt.seg = ttt.prf = ttt.sff = max(0, a[tl]);
ttt.sum = a[tl];
t[v] = ttt;
return;
}
int tm = (tl + tr) >> 1;
build(v+v, tl, tm);
build(v+v+1, tm+1, tr);
t[v] = combine(t[v+v], t[v+v+1]);
}
node get(int v, int tl, int tr, int l, int r){
if (tl >= l && tr <= r) return t[v];
if (tl > r || tr < l){
node c;
c.prf = c.sff = c.seg = -INF;
c.sum = 0;
return c;
}
int tm = (tl + tr) >> 1;
return combine(get(v+v, tl, tm, l, r), get(v+v+1, tm+1, tr, l, r));
}
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);
for (int j = 0; j < Q; ++j) {
C[j] = H[L[j]];
}
int N = H.size();
if (*max_element(H.begin(), H.end()) > 2 && N <= 5000){
for (int l = 0; l < N; l++){
long long mx = H[l];
for (int r = l; r < N; r++){
mx = max(mx, 1ll * H[r]);
MAX[l][r] = mx;
}
mx = H[l];
for (int i = l - 1; i >= 0; i--){
mx = max(mx, 1ll * H[i]);
MAX[l][i] = mx;
}
}
for (int i = 0; i < N; i++){
pref[i][0] = MAX[i][0];
for (int j = 1; j < N; j++){
pref[i][j] = pref[i][j - 1] + MAX[i][j];
}
}
for (int i = 0; i < Q; i++){
int l = L[i], r = R[i];
long long ans = 1e18;
for (int x = l; x <= r; x++){
long long k = pref[x][r];
if (l > 0) k -= pref[x][l - 1];
ans = min(ans, k);
}
C[i] = ans;
}
} else {
for (int i = 0; i < N; i++){
a[i + 1] = 1;
if (H[i] == 2) a[i + 1] = -INF;
}
build(1, 1, N);
for (int i = 0; i < Q; i++){
int l = L[i], r = R[i];
++l, ++r;
long long x = get(1, 1, N, l, r).seg;
long long y = (r - l + 1) - x;
C[i] = x + 2 * y;
//cout << x << ' ' << y << endl;
}
}
return C;
}
/*
7 5
1 2 1 1 2 2 1
1 1
1 4
3 6
6 6
0 6
*/
