#include <iostream>
#include <complex>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <functional>
#include <bitset>
#include <queue>
#include <map>
#include <stack>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <vector>
//#include "meetings.h"
using namespace std;
#define endl '\n'
#define db double
#define ll long long
#define pb push_back
#define fs first
#define sd second
#define Mod long(1e9 + 7)
#define all(x) x.begin(), x.end()
#define unvisited long(-1)
#define Eps double(1e-9)
#define _for(i, n) for(int i = 0; i < (n); i++)
#define dbg(x) cout << #x ": " << x << endl;
const ll Max = 1e6 + 7, Inf = 2e18 + 7LL;
void clear_vec(vector <ll> &v){
for(auto& u : v) u = 0;
}
vector<long long> minimum_costs(vector<int> H, vector<int> L, vector<int> R)
{
int n = H.size(), q = L.size();
vector <ll> v(n);
auto F = [&](int l, int r) -> ll
{
priority_queue <ll> h;
clear_vec(v);
ll sum = 0;
while(!h.empty()){
h.pop();
}
for(int i = l; i <= r; i++){
h.push(-H[i]); sum = sum + ((ll) H[i]);
while (!h.empty())
{
int x = abs(h.top());
if(H[i] > x){
sum += abs(H[i] - x);
h.pop();
} else break;
}
v[i] += sum;
}
sum = 0;
while(!h.empty()){
h.pop();
}
for(int i = r; i >= l; i--){
h.push(-H[i]); sum = sum + ((ll) H[i]);
while (!h.empty())
{
int x = abs(h.top());
if(H[i] > x){
sum += abs(H[i] - x);
h.pop();
} else break;
}
v[i] += sum;
}
ll sol = Inf;
for(int i = l; i <= r; i++){
sol = min(sol, v[i] - H[i]);
}
return sol;
};
vector <ll> ans(q);
for(int i = 0; i < q; i++){
//ans[i] = St.query(L[i], R[i]);
ans[i] = F(L[i], R[i]);
}
return ans;
}
