#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int mxN=1e5;
int n, q, b[mxN], c[mxN+1], st[1<<18];
ll c1[5000][5000], c2[5000][5000];
vector<int> a;
void bld(int i=1, int l2=0, int r2=n-1) {
if(l2==r2)
st[i]=c[l2+1]-l2-1;
else {
int m2=(l2+r2)/2;
bld(2*i, l2, m2);
bld(2*i+1, m2+1, r2);
st[i]=max(st[2*i], st[2*i+1]);
}
}
ll qry(int l1, int r1, int i=1, int l2=0, int r2=n-1) {
l1=max(l2, l1);
r1=min(r2, r1);
if(l1>r1)
return 0;
if(l1<=l2&&r2<=r1)
return st[i];
int m2=(l2+r2)/2;
return max(qry(l1, r1, 2*i, l2, m2), qry(l1, r1, 2*i+1, m2+1, r2));
}
vector<ll> minimum_costs(vector<int> h, vector<int> l, vector<int> r) {
n=h.size(), q=l.size();
vector<ll> ans(q);
if(n<=5000&&q<=5000) {
for(int i=0; i<n; ++i) {
int d=c1[i][i]=c2[i][i]=h[i];
for(int j=i-1; j>=0; --j) {
d=max(h[j], d);
c1[i][j]=d+c1[i][j+1];
}
d=h[i];
for(int j=i+1; j<n; ++j) {
d=max(h[j], d);
c2[i][j]=d+c2[i][j-1];
}
}
for(int i=0; i<q; ++i) {
ans[i]=LLONG_MAX;
for(int j=l[i]; j<=r[i]; ++j)
ans[i]=min(c1[j][l[i]]+c2[j][r[i]]-h[j], ans[i]);
}
} else {
for(int i=0; i<n; ++i) {
b[i]=i?b[i-1]:-1;
if(h[i]>1) {
a.push_back(i);
b[i]=i;
}
if(h[i]>2)
return ans;
}
c[n]=n;
for(int i=n-1; i>=0; --i)
c[i]=h[i]>1?i:c[i+1];
bld();
for(int i=0; i<q; ++i) {
int l2=c[l[i]], r2=b[r[i]];
ans[i]=l2>r[i]?r[i]-l[i]+1:max(l2-l[i], r[i]-r2);
if(l2<r2)
ans[i]=max(qry(l2, r2-1), ans[i]);
ans[i]=2*(r[i]-l[i]+1)-ans[i];
}
}
return ans;
}
