#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 = 1e16 + 7;
struct SegmentTree
{
struct node
{
ll val;
node(ll v = Inf)
{
val = v;
}
};
vector <node> tree; int l;
node merge(node a, node b)
{
return node(min(a.val, b.val));
}
void update(int k, int v)
{ k++;
k += (l - 1); tree[k] = node(v);
for(k /= 2; k > 0; k /= 2)
tree[k] = merge(tree[2*k], tree[2*k+1]);
}
node query(int k, int x, int y, int s, int e)
{
if(s > y || e < x)
return node();
if(s >= x && e <= y)
return tree[k];
int middle = (s + e) / 2;
return merge(query(2*k, x, y, s, middle),
query(2*k+1, x, y, middle + 1, e));
}
int query(int x, int y)
{ x++; y++;
node ans = query(1, x, y, 1, l);
return ans.val;
}
SegmentTree(int n)
{
for(l = 1; l < n; (l <<= 1));
tree.assign(2 * l, node());
}
};
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), H(n);
for(int i = 0; i < n; i++){
H[i] = _H[i];
}
auto F = [&](int l, int r) -> ll
{
priority_queue <pair<ll, ll>> h;
clear_vec(v);
ll sum = 0;
while(!h.empty()){
h.pop();
}
for(int i = l; i <= r; i++){
h.push({-H[i], 1}); sum += H[i];
while (!h.empty())
{
ll x = abs(h.top().fs), w = h.top().sd;
if(H[i] > x){
sum += abs(H[i] - x) * w;
h.pop();
ll tx = h.top().fs, ty = h.top().sd;
h.pop();
h.push({ tx, ty + w });
} else break;
}
v[i] += sum;
}
sum = 0;
while(!h.empty()){
h.pop();
}
for(int i = r; i >= l; i--){
h.push({-H[i], 1}); sum += H[i];
while (!h.empty())
{
ll x = abs(h.top().fs), w = h.top().sd;
if(H[i] > x){
sum += abs(H[i] - x) * w;
h.pop();
ll tx = h.top().fs, ty = h.top().sd;
h.pop();
h.push({ tx, ty + w });
} else break;
}
v[i] += sum;
}
ll sol = Inf;
for(int i = l; i <= r; i++){
sol = min(sol, v[i] - H[i]);
}
return sol;
};
SegmentTree St(n);
for(int i = 0; i < n; i++){
//St.update(i, v[i]);
//cerr << v[i] << " ";
}
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;
}
