#include "meetings.h"
#include "bits/stdc++.h"
using namespace std;
#ifndef EVAL
#include "grader.cpp"
#endif
#define ar array
typedef long long ll;
typedef int32_t ii;
//~ #define int ll
const int N = 1e5 + 5;
struct ST{
ar<ll, 2> tree[N << 2];
ar<ll, 2> def;
ST(){
def = (ar<ll, 2>){(ll)1e18, (ll)1e18};
}
void set(int i, ll v, int lx, int rx, int x){
if(lx == rx) { tree[x] = {v, lx}; return; }
int m = (lx + rx) >> 1;
if(i <= m) set(i, v, lx, m, x << 1);
else set(i, v, m + 1, rx, x << 1 | 1);
tree[x] = min(tree[x << 1], tree[x << 1 | 1]);
}
void set(int i, ll v){
set(i, v, 0, N, 1);
}
ar<ll, 2> get(int l, int r, int lx, int rx, int x){
if(lx > r || rx < l) return def;
if(lx >= l && rx <= r) return tree[x];
int m = (lx + rx) >> 1;
return min(get(l, r, lx, m, x << 1), get(l, r, m + 1, rx, x << 1 | 1));
}
ar<ll, 2> get(int l, int r){
return get(l, r, 0, N, 1);
}
}tree;
bool check = 1;
vector<ll> minimum_costs(vector<ii> a, vector<ii> l, vector<ii> r) {
int n = a.size(), q = l.size();
if(n <= 5000 && q <= 5000 && check){
vector<ll> res(q);
auto get = [&](vector<int> a){
int n = a.size();
ll cur = 0;
vector<int> ss;
vector<ll> cost(n);
for(int i=0;i<n;i++){
while(!ss.empty() && a[ss.back()] <= a[i]){
int id = ss.back();
ss.pop_back();
if(ss.empty()) cur -= a[id] * 1ll * (id + 1);
else cur -= a[id] * 1ll * (id - ss.back());
}
if(ss.empty()) cur += a[i] * 1ll * (i + 1);
else cur += a[i] * 1ll * (i - ss.back());
ss.push_back(i);
cost[i] += cur;
}
ss.clear(); cur = 0;
for(int i= n - 1;~i;i--){
while(!ss.empty() && a[ss.back()] <= a[i]){
int id = ss.back();
ss.pop_back();
if(ss.empty()) cur -= a[id] * 1ll * (n - id);
else cur -= a[id] * 1ll * (ss.back() - id);
}
if(ss.empty()) cur += a[i] * 1ll * (n - i);
else cur += a[i] * 1ll * (ss.back() - i);
ss.push_back(i);
cost[i] += cur;
}
ll mn = 1e18;
for(int i=0;i<n;i++){
mn = min(mn, cost[i] - a[i]);
}
return mn;
};
for(int i=0;i<q;i++){
vector<int> b;
for(int j=l[i];j<=r[i];j++){
b.push_back(a[j]);
}
res[i] = get(b);
}
return res;
}
vector<ll> res(q), cost(n);
vector<vector<int>> pref(n, vector<int>(20, -1)), suff(n, vector<int>(20, n + 1));
{
for(int i=0;i<n;i++){
if(i) pref[i] = pref[i - 1];
pref[i][a[i] - 1] = i;
}
for(int i=n-1;~i;i--){
if(i + 1 < n) suff[i] = suff[i + 1];
suff[i][a[i] - 1] = i;
}
}
auto get = [&](int i, int l, int r){
ll cost = 0;
for(int j=19;~j;j--){
if(l <= pref[i][j]){
cost += (pref[i][j] - l + 1) * 1ll * j;
l = pref[i][j] + 1;
}
if(suff[i][j] <= r){
cost += (r - suff[i][j] + 1) * 1ll * j;
r = suff[i][j] - 1;
}
}
cost -= (a[i] - 1);
return cost;
};
for(int i=0;i<n;i++){
cost[i] = get(i, 0, n - 1);
tree.set(i, cost[i]);
}
for(int i=0;i<q;i++){
int p = -1;
for(int j=19;~j;j--){
if(l[i] <= pref[r[i]][j]){
p = pref[r[i]][j];
break;
}
}
assert(~p);
int l_ = suff[l[i]][a[p] - 1], r_ = pref[r[i]][a[p] - 1];
vector<int> pos;
pos.push_back(tree.get(l_, r_)[1]);
for(int j=19;~j;j--){
if(suff[l[i]][j] < l_){
pos.push_back(tree.get(suff[l[i]][j], l_ - 1)[1]);
l_ = suff[l[i]][j];
}
if(r_ < pref[r[i]][j]){
pos.push_back(tree.get(r_ + 1, pref[r[i]][j])[1]);
r_ = pref[r[i]][j];
}
}
res[i] = 1e18;
for(auto x : pos){
res[i] = min(res[i], get(x, l[i], r[i]));
//~ cout<<x<<" ";
}
res[i] += (r[i] - l[i] + 1);
//~ cout<<"\n";
}
return res;
}
