#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
constexpr int MAXN = 100100;
constexpr int MAXH = 20;
constexpr ll INF = 4e18;
int n, h, q;
int a[MAXN], l[MAXN], r[MAXN];
ll C[MAXN];
struct Seg{
ll tree[MAXN*4], lazy[MAXN*4];
void init(int i, int l, int r){
lazy[i] = 0;
if (l==r) {tree[i] = C[l]; return;}
int m = (l+r)>>1;
init(i<<1, l, m); init(i<<1|1, m+1, r);
tree[i] = min(tree[i<<1], tree[i<<1|1]);
}
void propagate(int i, int l, int r){
if (!lazy[i]) return;
tree[i] += lazy[i];
if (l!=r){
lazy[i<<1] += lazy[i];
lazy[i<<1|1] += lazy[i];
}
lazy[i] = 0;
}
void update(int i, int l, int r, int s, int e, ll x){
propagate(i, l, r);
if (r<s || e<l) return;
if (s<=l && r<=e){
lazy[i] += x;
propagate(i, l, r);
return;
}
int m = (l+r)>>1;
update(i<<1, l, m, s, e, x); update(i<<1|1, m+1, r, s, e, x);
tree[i] = min(tree[i<<1], tree[i<<1|1]);
}
ll query(int i, int l, int r, int s, int e){
propagate(i, l, r);
if (r<s || e<l) return INF;
if (s<=l && r<=e) return tree[i];
int m = (l+r)>>1;
return min(query(i<<1, l, m, s, e), query(i<<1|1, m+1, r, s, e));
}
}tree;
struct Foo{
int L[MAXN], R[MAXN];
void init(int k){
int prv = 0;
for (int i=1;i<=n;i++) if (a[i]>=k){
L[i] = R[i] = 0;
C[i] += n;
for (int j=prv+1;j<i;j++){
L[j] = prv+1, R[j] = i-1;
C[j] += n - (i-prv-1);
}
prv = i;
}
for (int j=prv+1;j<n+1;j++){
L[j] = prv+1, R[j] = n;
C[j] += n - (n+1-prv-1);
}
}
void query(int l, int r, int typ){
if (L[l]){
tree.update(1, 1, n, l, min(r, R[l]), (l-L[l]) * typ);
}
if (R[r]){
tree.update(1, 1, n, max(l, L[r]), r, (R[r]-r) * typ);
}
}
}F[MAXH+1];
std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L,
std::vector<int> R) {
n = H.size();
q = L.size();
h = *max_element(H.begin(), H.end());
for (int i=1;i<=n;i++){
a[i] = H[i-1];
}
for (int i=1;i<=q;i++){
l[i] = L[i-1] + 1;
r[i] = R[i-1] + 1;
}
for (int i=1;i<=h;i++) F[i].init(i);
vector<ll> ans;
tree.init(1, 1, n);
for (int i=1;i<=q;i++){
for (int j=1;j<=h;j++) F[j].query(l[i], r[i], 1);
ans.push_back(tree.query(1, 1, n, l[i], r[i]) - (ll)h * (n-(r[i]-l[i]+1)));
for (int j=1;j<=h;j++) F[j].query(l[i], r[i], -1);
}
return ans;
}
