#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
const int MXN = 100005;
int segT[4*MXN];
int lb[4*MXN];
int rb[4*MXN];
int pre[MXN];
int nxt[MXN];
vector<int> occurs;
void build(int c, int l, int r){
lb[c] = l;
rb[c] = r;
if(l == r){
segT[c] = pre[l] - nxt[l];
return;
}
int k = (l + r)/2;
build(2*c,l,k);
build(2*c+1,k+1,r);
segT[c] = min(segT[2*c], segT[2*c+1]);
}
int query(int c, int l, int r){
if(lb[c] == l && rb[c] == r) return segT[c];
int k = (lb[c] + rb[c])/2;
if(l <= k && k < r) return min(query(2*c,l,k), query(2*c+1,k+1,r));
else if(r <= k) return query(2*c,l,r);
else return query(2*c+1,l,r);
}
long long costs[5005][5005];
vector<long long> minimum_costs(vector<int> H, vector<int> L,
vector<int> R) {
int Q = L.size();
vector<long long> C(Q);
int N = H.size();
if(N <= 5000){
// Sol 1: Preprocess the N^2 possibilities and then loop for selection.
for(int i = 0; i < N; i++){
// Starting at i.
int cur = H[i];
costs[i][i] = 0ll;
for(int j = i-1; j >= 0; j--){
cur = max(cur, H[j]);
costs[i][j] = costs[i][j+1] + (long long)cur;
}
cur = H[i];
for(int j = i+1; j < N; j++){
cur = max(cur, H[j]);
costs[i][j] = costs[i][j-1] + (long long)cur;
}
}
for(int i = 0; i < Q; i++){
C[i] = 1e18;
for(int j = L[i]; j <= R[i]; j++){
C[i] = min(C[i],costs[j][L[i]] + costs[j][R[i]] + (long long)H[j]);
}
}
}else{
// Sol 2: Use segment tree to answer RMQ of a derived parameter 'prev - next + 3 + 2R - 2L'.
for(int i = 0; i < N; i++){
if(H[i] == 2) occurs.push_back(i);
}
for(int i = 0; i < N; i++){
if(H[i] == 2){
pre[i] = nxt[i] = i;
continue;
}
if(i > occurs.front())
pre[i] = *(lower_bound(occurs.begin(), occurs.end(), i)-1);
if(i < occurs.back())
nxt[i] = *upper_bound(occurs.begin(), occurs.end(), i);
}
build(1,0,N-1);
for(int i = 0; i < Q; i++){
int idx = lower_bound(occurs.begin(), occurs.end(), L[i]) - occurs.begin();
if(idx == occurs.size() || occurs[idx] > R[i]){
// Not found any 2's in there
C[i] = R[i] - L[i] + 1;
}else{
// 3 Cases: f, mid, s
int lidx = upper_bound(occurs.begin(), occurs.end(), R[i]) - 1 - occurs.begin();
// Case f
int a1 = 2*R[i] - occurs[idx] - L[i] + 2;
// Case mid
int a2 = query(1,occurs[idx],occurs[lidx]) + 3 + 2*R[i] - 2*L[i];
// Case s
int a3 = occurs[lidx] - 2*L[i] + 2 + R[i];
C[i] = min(a1,min(a2,a3));
}
}
}
return C;
}
