#include "meetings.h"
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define MP make_pair
#define pll pair <ll,ll>
#define fi first
#define se second
#define sz(a) (ll((a).size()))
#define BIT(mask,i) (((mask) >> (i))&1LL)
#define MASK(i) (1LL << (i))
ll n,q;
const ll MAXN = 7.5e5+100;
const ll INF = 1e18;
ll c[MAXN];
ll a[MAXN];
ll INF1 = 1e9+7;
namespace seg{
ll tree[MAXN*4],lazy[MAXN*4];
void build(ll id = 1,ll l = 1,ll r = n){
if (l == r)tree[id] = c[l];
else{
ll mid = (l + r) >> 1;
build(id<<1,l,mid);
build(id<<1|1,mid+1,r);
tree[id] = min(tree[id<<1],tree[id<<1|1]);
}
}
void push(ll id,ll val){
tree[id]+=val;
lazy[id]+=val;
}
void lz(ll id){
if (lazy[id]){
push(id<<1,lazy[id]);
push(id<<1|1,lazy[id]);
lazy[id] = 0;
}
}
void update(ll id,ll l,ll r,ll l1,ll r1,ll val){
if (l > r1 || l1 > r || l1 > r1)return;
if (l1 <= l && r <= r1){
push(id,val);
return;
}
lz(id);
ll mid = (l + r) >> 1;
update(id << 1,l,mid,l1,r1,val);
update(id<<1|1,mid+1,r,l1,r1,val);
tree[id] = min(tree[id<<1],tree[id<<1|1]);
}
ll get(ll id,ll l,ll r,ll l1,ll r1){
if (l > r1 || l1 > r)return INF;
if (l1 <= l && r <= r1)return tree[id];
ll mid = (l + r) >> 1;
lz(id);
return min(get(id<<1,l,mid,l1,r1),get(id<<1|1,mid+1,r,l1,r1));
}
}
ll solve(ll l,ll r){
vector <ll> all;
ll cur = 0;
all.push_back(l-1);
swap(INF1,a[l-1]);
for (ll i = l;i <= r;i ++){
while (a[all.back()] < a[i]){
cur -= (all[sz(all) - 1] - all[sz(all) - 2]) * a[all[sz(all) - 1]];
all.pop_back();
}
all.push_back(i);
cur += (all[sz(all) - 1] - all[sz(all) - 2]) * a[all[sz(all) - 1]];
c[i] = cur;
}
swap(INF1,a[l-1]);
cur = 0;
all.clear();
all.push_back(r+1);
swap(INF1,a[r+1]);
for (ll i = r;i >= l;i --){
while (a[all.back()] < a[i]){
cur -= (- all[sz(all) - 1] + all[sz(all) - 2]) * a[all[sz(all) - 1]];
all.pop_back();
}
all.push_back(i);
cur += (- all[sz(all) - 1] + all[sz(all) - 2]) * a[all[sz(all) - 1]];
c[i] += cur;
}
swap(INF1,a[r+1]);
ll res = 1e18;
for (ll i = l;i <= r;i ++){c[i] -= a[i];res = min(res,c[i]);}
return res;
}
set <int> s[21];
std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L,
std::vector<int> R){
n = sz(H);
q = sz(L);
ll max_ai = 0;
for (ll i = 1;i <= n;i ++){
a[i] = H[i-1];
max_ai = max(max_ai,a[i]);
}
vector <ll> res(q);
if (max_ai <= 20){
for (ll j = 1;j <= 20;j ++){
s[j].insert(0);
s[j].insert(n+1);
}
for (ll i = 1;i <= n;i ++){
for (ll j = 1;j <= a[i];j ++)s[j].insert(i);
}
solve(1,n);
seg::build();
// cout<<"OK"<<endl;
}
if (max_ai <= 20){
vector <pair <pll,ll> > all;
for (ll i = 0;i < q;i ++)all.push_back(MP(MP(L[i]+1,R[i]+1),i));
sort(all.begin(),all.end());
for (ll i = 1,ptr = 0;i <= n;i ++){
if (i >= 2){
for (ll j = 1;j <= 20;j ++){
auto l1 = s[j].lower_bound(i-1);
seg::update(1,1,n,*l1,n,-1);
}
}
while (ptr < sz(all) && all[ptr].fi.fi == i){
ll r = all[ptr].fi.se,l = all[ptr].fi.fi;
for (ll j = 1;j <= 20;j ++){
auto r1 = s[j].upper_bound(r);
seg::update(1,1,n,l,r, -(n-*r1+1));
seg::update(1,1,n,l,*prev(r1), -(*r1-r-1));
}
res[all[ptr].se] = seg::get(1,1,n,l,r);
for (ll j = 1;j <= 20;j ++){
auto r1 = s[j].upper_bound(r);
seg::update(1,1,n,l,r, +(n-*r1+1));
seg::update(1,1,n,l,*prev(r1), +(*r1-r-1));
}
ptr++;
}
}
}
else{
for (ll i = 0;i < q;i ++){
ll l = L[i] + 1,r = R[i] + 1;
if (n <= 5000 && q <= 5000){
res[i] = solve(l,r);
}
}
}
return res;
}
