#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pi;
typedef pair<int,pi> pii;
ll N, Q;
ll mount[1000005];
struct node{
node *left = nullptr, *right = nullptr;
int S, E, pre1 = 0, suff1 = 0, seg1 = 0;
node(int _s, int _e){
S = _s;
E = _e;
if (S == E){
pre1 = suff1 = seg1 = (mount[S] == 1);
return;
}
left = new node(S,(S+E)/2);
right = new node((S+E)/2+1,E);
if (left->pre1 == left->E - left->S + 1){
pre1 = left->pre1 + right->pre1;
}
else pre1 = left->pre1;
if (right->suff1 == right->E - right->S + 1){
suff1 = right->suff1 + right->suff1;
}
else suff1 = right->suff1;
seg1 = max(left->seg1,right->seg1);
seg1 = max(seg1,left->suff1 + right->pre1);
}
pii query(int l, int r){
if (l > E || r < S || r < l) return pii(0,pi(0,0));
if (l <= S && E <= r) return pii(seg1,pi(pre1,suff1));
pii l1 = left->query(l,min(r,(S+E)/2)), r1 = right->query(max((S+E)/2+1,l),r);
int sg = max(max(l1.first,r1.first),l1.second.second+r1.second.first);
int pr, su;
if (l1.second.first == max(0,left->E-l+1)){
pr = l1.second.first + r1.second.first;
}
else pr = l1.second.first;
if (r1.second.second == max(0,r-right->S+1)){
su = r1.second.second + l1.second.second;
}
else su = r1.second.second;
return pii(sg,pi(pr,su));
}
} *root;
vector<ll> minimum_costs(vector<int> H, vector<int> L, vector<int> R) {
vector<ll> ans;
N = H.size();
Q = L.size();
for (int i = 0; i < N; ++i){
mount[i] = H[i];
}
if (N <= 5000){
for (int i = 0; i < Q; ++i){
ll maxi = 0;
vector<ll> pos;
pos.resize(R[i]-L[i]+1,0);
for (ll j = L[i]; j <= R[i]; ++j){
maxi = max(maxi,mount[j]);
pos[j-L[i]] += (j-L[i]+1)*maxi;
}
maxi = 0;
for (ll j = R[i]; j >= L[i]; --j){
maxi = max(maxi,mount[j]);
pos[j-L[i]] += (R[i]-j+1)*maxi;
}
ll mini = 1e17;
for (int j = 0; j < R[i]-L[i]+1; ++j){
mini = min(mini,pos[j]);
}
ans[i] = mini;
}
}
else{
root = new node(0,N-1);
for (int i = 0; i < Q; ++i){
ans.push_back(2*(R[i]-L[i]+1)-root->query(L[i],R[i]).first);
}
return ans;
}
}
