#include "meetings.h"
#include<bits/stdc++.h>
using namespace std;
const long long inf=99999999999999999LL;
long long a,b,c,d,e,i,j,ii,jj,zx,xc,tes,t,f[750009],pas;
pair <long long, long long> Q[750009];
vector <long long> ANS;
long long Lf[5003][5003],Rg[5003][5003];
vector<long long> minimum_costs(vector<int> H, vector<int> L, vector<int> R) {
a=H.size();
tes=L.size();
for(i=1; i<=a; i++){
f[i]=H[i-1];
}
for(t=1; t<=tes; t++){
Q[t].first=L[t-1]+1;
Q[t].second=R[t-1]+1;
}
if(a<=5000&&tes<=5000){
for(i=1; i<=a; i++){
zx=0;xc=0;
for(j=i; j>=1; j--){
if(xc<f[j]) xc=f[j];
zx+=xc;
Lf[i][j]=zx;
}
}
for(i=1; i<=a; i++){
zx=0;xc=0;
for(j=i; j<=a; j++){
if(xc<f[j]) xc=f[j];
zx+=xc;
Rg[i][j]=zx;
}
}
for(t=1; t<=tes; t++){
zx=inf;
for(i=Q[t].first; i<=Q[t].second; i++){
if(zx>Lf[i][Q[t].first]+Rg[i][Q[t].second]-f[i]){
zx=Lf[i][Q[t].first]+Rg[i][Q[t].second]-f[i];
}
}
ANS.push_back(zx);
}
return ANS;
}
return ANS;
}
/*int main(){
ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
vector <int> H,L,R;
cin>>a>>tes;
for(i=1; i<=a; i++){
cin>>c;
H.push_back(c);
}
for(t=1; t<=tes; t++){
cin>>c>>d;
L.push_back(c);
R.push_back(d);
}
ANS=minimum_costs(H,L,R);
for(t=0; t<ANS.size(); t++){
cout<<ANS[t]<<" ";
}
return 0;
}*/
