#include "meetings.h"
#include <bits/stdc++.h>
//#include "grader.cpp"
using namespace std;
typedef long long ll;
ll n,q,v[100005],rmq[21][100005],loga[100005];
ll s[5005][5005];
ll getmax(ll l,ll r)
{
ll lg=loga[r-l+1];
return max(rmq[lg][l],rmq[lg][r-(1<<lg)+1]);
}
std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L,std::vector<int> R)
{
n=H.size();
for(int i=1;i<=n;i++)
{
v[i]=H[i-1];
for(int bit=0;bit<=20;bit++)
if((1<<bit)<=i)
loga[i]=bit;
}
for(int i=n;i>=1;i--)
{
rmq[0][i]=v[i];
for(int j=1;j<=20;j++)
{
rmq[j][i]=rmq[j-1][i];
int poz=i+(1<<(j-1));
if(poz<=n)
rmq[j][i]=max(rmq[j][i],rmq[j-1][poz]);
}
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
ll st=min(i,j);
ll dr=max(i,j);
ll val=getmax(st,dr);
s[i][j]=s[i][j-1]+val;
}
}
vector<ll> sol;
q=L.size();
for(int z=0;z<q;z++)
{
int l=L[z]+1;
int r=R[z]+1;
ll ans=1e18;
for(int i=l;i<=r;i++)
ans=min(ans,s[i][r]-s[i][l-1]);
sol.push_back(ans);
}
return sol;
}
