#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/rope>
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;
typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;
typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;
template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;
#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)
#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
const int MOD = 1000000007;
const ll INF = 1e18;
const int MX = 1<<20;
const int SZ = 750001;
#include "meetings.h"
pl operator*(const pl& l, const ll& r) { return {l.f*r,l.s*r}; }
pl operator+(const pl& l, const pl& r) { return {l.f+r.f,l.s+r.s}; }
pl operator+=(pl& l, const pl& r) { return l = {l.f+r.f,l.s+r.s}; }
int N;
vpi hei;
void checkmn(ll& x, ll y) { x = min(x,y); }
struct RMQ {
int mx[SZ][21];
int bet(int a, int b) {
return hei[a] > hei[b] ? a : b;
}
RMQ() {
F0R(i,N) mx[i][0] = i;
FOR(j,1,21) F0R(i,N-(1<<j)+1)
mx[i][j] = bet(mx[i][j-1],mx[i+(1<<(j-1))][j-1]);
}
int query(int L, int R) {
int x = 31-__builtin_clz(R-L+1);
return bet(mx[L][x],mx[R-(1<<x)+1][x]);
}
};
RMQ RM;
ll ans[SZ];
vector<array<int,3>> tmp[SZ];
struct line {
int s,e;
ll m,b;
line() {}
line(int _s, int _e, ll _m, ll _b) { s = _s, e = _e, m = _m, b = _b; }
ll eval(int x) { return m*x+b; }
};
line d[SZ];
struct lineContain {
int s,e;
ll lazy = 0;
lineContain(int _s, int _e) {
s = _s, e = _e;
}
ll evalBack() {
if (!size()) return 0;
return d[e].eval(d[e].e)+lazy;
}
line front() {
line l = d[s]; l.b += lazy;
return l;
}
line back() {
line l = d[e]; l.b += lazy;
return l;
}
line pop_front() {
line l = front(); s ++;
return l;
}
line pop_back() {
line l = back(); e --;
return l;
}
ll get(int m) {
if (size() == 0 || m < d[s].s) return 0;
int lo = s, hi = e;
while (lo < hi) {
int mid = (lo+hi+1)/2;
if (d[mid].s <= m) lo = mid;
else hi = mid-1;
}
return d[lo].eval(m)+lazy;
}
ll evalFront(ll x) {
return d[s].eval(x)+lazy;
}
void push_back(line l) {
l.b -= lazy;
d[++e] = l;
}
void push_front(line l) {
l.b -= lazy;
d[--s] = l;
}
int size() { return e-s+1; }
};
lineContain divi(int lo, int hi) {
if (lo > hi) return lineContain(lo,lo-1);
ll x = RM.query(lo,hi);
auto l = divi(lo,x-1); auto r = divi(x+1,hi);
for (auto y: tmp[x]) checkmn(ans[y[2]],(ll)(x-y[0]+1)*hei[x].f+r.get(y[1]));
r.lazy += (x-lo+1)*hei[x].f;
int right = x;
ll lst = l.evalBack();
while (sz(r)) {
ll e = r.front().e;
ll a = lst+(e-x+1)*hei[x].f;
ll b = r.evalFront(e);
if (a <= b) {
right = e; r.pop_front();
continue;
} else {
ll s = r.front().s;
while (s < e) {
ll m = (s+e)/2;
a = lst+(m-x+1)*hei[x].f;
b = r.evalFront(m);
if (a <= b) s = m+1;
else e = m;
}
right = s-1;
auto a = r.pop_front(); a.s = s; r.push_front(a);
break;
// binary search
}
}
l.pb(line(x,right,hei[x].f,lst-hei[x].f*(x-1)));
if (sz(l) > sz(r)) {
while (sz(r)) l.pb(r.pop_front());
return l;
} else {
while (sz(l)) r.push_front(l.pop_back());
return r;
}
}
void solve(vi L, vi R) {
RM = RMQ();
vi h; F0R(i,N) h.pb(i);
sort(all(h),[](int a, int b) { return hei[a] < hei[b]; });
F0R(i,SZ) tmp[i].clear();
F0R(i,sz(L)) tmp[RM.query(L[i],R[i])].pb({L[i],R[i],i});
divi(0,N-1);
}
std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L,
std::vector<int> R) {
N = sz(H);
F0R(i,N) hei.pb({H[i],i});
F0R(i,sz(L)) ans[i] = INF;
solve(L,R);
reverse(all(hei));
F0R(i,sz(L)) {
L[i] = sz(H)-1-L[i];
R[i] = sz(H)-1-R[i];
swap(L[i],R[i]);
}
// cout << "\n";
solve(L,R);
vl ret; F0R(i,sz(L)) ret.pb(ans[i]);
return ret;
}
/*
int main() {
int N,Q; cin >> N >> Q;// N = Q = 750000;
vi H(N), L(Q), R(Q);
F0R(i,N) {
// H[i] = rand() % 1000000000;
cin >> H[i];
}
F0R(i,Q) {
L[i] = rand() % N, R[i] = rand() % N;
if (L[i] > R[i]) swap(L[i],R[i]);
cin >> L[i] >> R[i];
}
vl C = minimum_costs(H, L, R);
for (auto a: C) cout << a << " ";
}*/
