#include "meetings.h"
#include <bits/stdc++.h>
#define N 100005
using namespace std;
struct SegTree{
vector<long long> t,lazy;
int n;
SegTree(int size){
n = size;
t.assign(4*n,0);
lazy.assign(4*n,0);
}
void push(int v){
t[v*2] += lazy[v];
t[v*2+1] += lazy[v];
lazy[v*2] += lazy[v];
lazy[v*2+1] += lazy[v];
lazy[v] = 0;
}
void upd(int v,int tl,int tr,int l,int r,long long val){
if(tr < l || r < tl){
return;
}
if(l <= tl && tr <= r){
t[v] += val;
lazy[v] += val;
return;
}
push(v);
int tm = (tl + tr)/2;
upd(v*2,tl,tm,l,r,val);
upd(v*2+1,tm+1,tr,l,r,val);
t[v] = min(t[v*2],t[v*2+1]);
}
long long get(int v,int tl,int tr,int l,int r){
if(tr < l || r < tl){
return 1e18;
}
if(l <= tl && tr <= r){
return t[v];
}
push(v);
int tm = (tl + tr)/2;
return min(get(v*2,tl,tm,l,r),get(v*2+1,tm+1,tr,l,r));
}
void upd(int l,int r,long long val){
upd(1,0,n-1,l,r,val);
}
long long get(int l,int r){
return get(1,0,n-1,l,r);
}
};
int lval[N][2];
int rval[N][2];
vector<int> pos[N];
vector<long long> minimum_costs(vector<int> h, vector<int> l, vector<int> r) {
int q = l.size();
int n = h.size();
SegTree t(n);
int maxi = 0;
for(int i = 0;i<n;i++){
maxi = max(maxi,h[i]);
t.upd(i,i,-h[i]);
}
vector<int> st0,st1;
for(int i = 0;i<n;i++){
while(st0.size() && h[st0.back()] <= h[i])
st0.pop_back();
while(st1.size() && h[st1.back()] < h[i])
st1.pop_back();
lval[i][0] = lval[i][1] = -1;
if(st0.size()){
lval[i][0] = st0.back();
}
if(st1.size()){
lval[i][1] = st1.back();
}
st0.push_back(i);
st1.push_back(i);
}
st0.clear(),st1.clear();
for(int i = n-1;i>=0;i--){
while(st0.size() && h[st0.back()] <= h[i])
st0.pop_back();
while(st1.size() && h[st1.back()] < h[i])
st1.pop_back();
rval[i][0] = rval[i][1] = n;
if(st0.size()){
rval[i][0] = st0.back();
}
if(st1.size()){
rval[i][1] = st1.back();
}
st0.push_back(i);
st1.push_back(i);
}
//cout << endl;
for(int i = 0;i<n;i++){
//cout << i << " " << rval[i][1] << " " << lval[i][0] << endl;
t.upd(i,rval[i][1] - 1,(long long)h[i] * (i - lval[i][0]));
t.upd(lval[i][1] + 1,i,(long long)h[i] * (rval[i][0] - i));
}
for(int i = 0;i<n;i++){
pos[h[i]].push_back(i);
}
for(int i = 1;i<=maxi;i++){
pos[i].push_back(n);
}
// for(int i = 0;i<n;i++){
// cout << t.get(i,i) << " ";
// }
// cout << endl;
vector<long long> res(q);
for(int i = 0;i<q;i++){
vector<pair<pair<int,int>,long long>> changes;
for(int j = 1;j<=maxi;j++){
int lpos,rpos;
if(pos[j][0] < l[i]){
lpos = prev(lower_bound(pos[j].begin(),pos[j].end(),l[i])) - pos[j].begin();
long long val = (long long)(pos[j][lpos] - lval[pos[j][lpos]][0]) * j;
changes.push_back({ {pos[j][lpos], rval[pos[j][lpos]][1]-1} ,-val});
}
if(pos[j].size() > 1 && pos[j][pos[j].size() - 2] > r[i]){
rpos = upper_bound(pos[j].begin(),pos[j].end(),r[i]) - pos[j].begin();
long long val = (long long)(rval[pos[j][rpos]][0] - pos[j][rpos]) * j;
changes.push_back({ { lval[pos[j][rpos]][1]+1,pos[j][rpos]} ,-val});
}
if(*lower_bound(pos[j].begin(),pos[j].end(),l[i]) > r[i])continue;
lpos = lower_bound(pos[j].begin(),pos[j].end(),l[i]) - pos[j].begin();
rpos = prev(upper_bound(pos[j].begin(),pos[j].end(),r[i])) - pos[j].begin();
if(lval[pos[j][lpos]][0] + 1 < l[i]){
long long val = (long long)(l[i] - lval[pos[j][lpos]][0] - 1) * j;
int ll = lpos,rr = rpos;
while(ll < rr){
int m = (ll + rr + 1)/2;
if(lval[pos[j][m]][0] < l[i]){
ll = m;
}
else rr = m-1;
}
changes.push_back({ {pos[j][lpos], rval[pos[j][ll]][1]-1} ,-val});
}
if(rval[pos[j][rpos]][0] - 1 > r[i]){
long long val = (long long)(rval[pos[j][rpos]][0] - r[i] - 1) * j;
int ll = lpos,rr = rpos;
while(ll < rr){
int m = (ll + rr)/2;
if(rval[pos[j][m]][0] > r[i]){
rr = m;
}
else ll = m+1;
}
changes.push_back({ { lval[pos[j][ll]][1]+1,pos[j][rpos]} ,-val});
}
}
for(auto u:changes){
t.upd(u.first.first,u.first.second,u.second);
}
// for(int i = 0;i<n;i++){
// cout << t.get(i,i) << " ";
// }
// cout << endl;
res[i] = t.get(l[i],r[i]);
for(auto u:changes){
t.upd(u.first.first,u.first.second,-u.second);
}
}
return res;
}
