#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll inf = 1e18;
const int maxn = 1e5 + 10;
ll dp[maxn];
struct node{
int pre = 0;
int suf = 0;
int sum = 0;
bool fil = 0;
} seg[4*maxn];
node merge(node a, node b){
node ret;
ret.pre = a.pre + (a.fil * b.pre);
ret.suf = b.suf + (b.fil * a.suf);
ret.fil = (a.fil & b.fil);
ret.sum = max({a.sum, b.sum, a.suf+b.pre});
return ret;
}
node get(int id, int L, int R, int l, int r){
if (l <= L and R <= r)
return seg[id];
int mid = (L + R) >> 1;
if (r <= mid)
return get(2*id+0, L, mid, l, r);
if (mid <= l)
return get(2*id+1, mid, R, l, r);
return merge(get(2*id+0, L, mid, l, r), get(2*id+1, mid, R, l, r));
}
void add(int id, int L, int R, int idx){
if (idx < L or R <= idx)
return;
if (L+1 == R){
seg[id].pre = seg[id].suf = seg[id].sum = seg[id].fil = 1;
return;
}
int mid = (L + R) >> 1;
add(2*id+0, L, mid, idx);
add(2*id+1, mid, R, idx);
seg[id] = merge(seg[2*id+0], seg[2*id+1]);
}
vector<ll> minimum_costs(vector<int> H, vector<int> L, vector<int> R) {
int n = H.size(), Q = L.size();
if (n <= 5000 and Q <= 5000){
vector<ll> C(Q);
for (int j = 0; j < Q; j++){
C[j] = inf;
stack<pair<int,int>> S;
ll Sum = 0;
for (int i = L[j]; i <= R[j]; i++){
int cnt = 1;
while (!S.empty() and S.top().first <= H[i]){
Sum -= 1LL*S.top().first*S.top().second;
cnt += S.top().second;
S.pop();
}
Sum += 1LL*H[i]*cnt;
dp[i] = Sum;
S.push({H[i],cnt});
}
while (!S.empty())
S.pop();
Sum = 0;
for (int i = R[j]; i >= L[j]; i--){
int cnt = 1;
while (!S.empty() and S.top().first <= H[i]){
Sum -= 1LL*S.top().first*S.top().second;
cnt += S.top().second;
S.pop();
}
Sum += 1LL*H[i]*cnt;
C[j] = min(C[j], Sum+dp[i]-H[i]);
S.push({H[i],cnt});
}
}
return C;
}
if (*max_element(H.begin(),H.end()) <= 2){
for (int i = 0; i < n; i++)
if (H[i] == 1)
add(1, 0, n, i);
vector<ll> C(Q);
for (int q = 0; q < Q; q++){
int len = R[q]-L[q]+1;
C[q] = 2*len - get(1, 0, n, L[q], R[q]+1).sum;
}
return C;
}
}
