#include <bits/stdc++.h>
#ifndef ARTHUR_LOCAL
#include "meetings.h"
#endif
using namespace std;
using ll = long long;
const int p2 = 4096;
const int MAXN = 3000;
int max_segtree[p2+p2];
ll sum_segtree[MAXN][p2+p2];
int RMQ(int l, int r)
{
l += p2;
r += p2;
if(l>r) swap(l,r);
int ans=0;
while(l<=r)
{
if(l%2 == 1) ans=max(ans,max_segtree[l++]);
if(r%2 == 0) ans=max(ans,max_segtree[r--]);
l/=2;
r/=2;
}
return ans;
}
ll query(int tree, int l, int r)
{
l += p2;
r += p2;
if(l>r) swap(l,r);
ll ans=0;
while(l<=r)
{
if(l%2 == 1) ans+=sum_segtree[tree][l++];
if(r%2 == 0) ans+=sum_segtree[tree][r--];
l/=2;
r/=2;
}
return ans;
}
vector<ll> minimum_costs(vector<int> H, vector<int> L, vector<int> R)
{
// int Q = L.size();
// std::vector<long long> C(Q);
// for (int j = 0; j < Q; ++j) {
// C[j] = H[L[j]];
// }
// return C;
int q = L.size();
int n = H.size();
for(int i=0; i<n; i++)
{
max_segtree[i+p2]=H[i];
}
for(int i=p2-1; i>=1; i--)
{
max_segtree[i]=max(max_segtree[i+i],max_segtree[i+i+1]);
}
for(int i=0; i<n; i++)
{
for(int j=0; j<n; j++)
{
sum_segtree[i][j+p2]=ll(RMQ(i,j));
}
}
for(int i=0; i<n; i++)
{
for(int j=p2-1; j>=1; j--)
{
sum_segtree[i][j] = sum_segtree[i][j+j] + sum_segtree[i][j+j+1];
}
}
vector<ll> ans;
for(int i=0; i<q; i++)
{
ll cur = 1e18;
for(int j=L[i]; j<=R[i]; j++)
{
cur = min(cur, query(i,L[i],R[i]));
}
ans.push_back(cur);
}
return ans;
}
