#include "meetings.h"
//#include "grader.cpp"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define mk make_pair
#define fr first
#define sc second
#define pi pair < int, int >
const int N = 1e5 + 7;
const int INF = 1e9 + 7;
int t[4 * N], lz[4 * N];
int prv[N][22], nxt[N][22];
int pr[N][22], prc[N][22], total[N];
int a[N], ans[N];
int n, q;
pair < pi, int > qr[N];
vector < ll > ret;
void push (int v, int l, int r){
if (l != r){
lz[v + v] += lz[v];
lz[v + v + 1] += lz[v];
}
t[v] += lz[v];
lz[v] = 0;
}
void upd (int v, int l, int r, int ql, int qr, int val){
push(v, l, r);
if (r < ql || qr < l)
return;
if (ql <= l && r <= qr){
lz[v] += val;
push(v, l, r);
return;
}
int mid = (l + r) >> 1;
upd(v + v, l, mid, ql, qr, val);
upd(v + v + 1, mid + 1, r, ql, qr, val);
t[v] = min(t[v + v], t[v + v + 1]);
}
int get (int v, int l, int r, int ql, int qr){
push(v, l, r);
if (r < ql || qr < l)
return INF;
if (ql <= l && r <= qr)
return t[v];
int mid = (l + r) >> 1;
return min(get(v + v, l, mid, ql, qr), get(v + v + 1, mid + 1, r, ql, qr));
}
void build (int v, int l, int r){
if (l == r){
int last = n + 1;
for (int j = 20; j >= 1; j--){
prc[l][j] = last - l;
if (last > nxt[l][j]){
pr[l][j] = (last - nxt[l][j]) * j;
t[v] += pr[l][j];
last = nxt[l][j];
}
}
total[l] = t[v];
last = 0;
for (int j = 20; j >= 1; j--){
if (last < prv[l][j]){
t[v] += (prv[l][j] - last) * j;
last = prv[l][j];
}
}
t[v] -= a[l];
}
else {
int mid = (l + r) >> 1;
build(v + v, l, mid);
build(v + v + 1, mid + 1, r);
t[v] = min(t[v + v], t[v + v + 1]);
}
}
void change (int l){
int last = n + 1;
for (int j = 20; j >= 1; j--){
if (last > nxt[l][j]){
upd(1, 1, n, nxt[l][j], last - 1, -j);
last = nxt[l][j];
}
}
}
vector<long long> minimum_costs(vector<int> H, vector<int> L, vector<int> R) {
n = H.size();
q = L.size();
for (int i = 0; i < n; i++)
a[i + 1] = H[i];
for (int i = 1; i <= n; i++){
for (int j = 1; j <= 20; j++)
prv[i][j] = prv[i - 1][j];
prv[i][a[i]] = i;
}
for (int j = 1; j <= 20; j++)
nxt[n + 1][j] = n + 1;
for (int i = n; i >= 1; i--){
for (int j = 1; j <= 20; j++)
nxt[i][j] = nxt[i + 1][j];
nxt[i][a[i]] = i;
}
build(1, 1, n);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= 20; j++)
pr[i][j] += pr[i][j - 1];
for (int i = 0; i < q; i++)
qr[i + 1] = {{L[i] + 1, R[i] + 1}, i + 1};
sort(qr + 1, qr + 1 + q);
int l = 1;
for (int i = 1; i <= q; i++){
while (qr[i].fr.fr > l){
change(l);
l++;
}
int r = qr[i].fr.sc, last = l - 1, res = INF;
for (int j = 20; j >= 1; j--){
if (last < prv[r][j] && prv[r][j] >= l){
res = min(res, get(1, 1, n, last + 1, prv[r][j]) - (total[r + 1] - pr[r + 1][j] + prc[r + 1][j] * j));
last = prv[r][j];
}
}
ans[qr[i].sc] = res;
}
for (int i = 1; i <= q; i++)
ret.pb(1ll * ans[i]);
return ret;
}
