#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define int ll
#define pii pair<int, int>
#define pb push_back
#define f first
#define s second
#define REP(i,n) for (int i = 0; i<n; ++i)
#define REP1(i,n) for (int i = 1; i<=n; ++i)
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) (int)(x).size()
#define MX(a,b) a = max(a,b)
#ifdef BALBIT
#define bug(...) cerr<<"#"<<__LINE__<<"- "<<#__VA_ARGS__<<": ", _do(__VA_ARGS__)
template<typename T> void _do(T && x) {cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T && x, S && ...y) {cerr<<x<<", "; _do(y...);}
#else
#define bug(...)
#endif // BALBIT
const int maxn = 1e5+5;
vector<int> pos[21];
struct zsk{
ll s[maxn*2];
ll QU(int l, int r) {
// range max query
ll re = 0;
for (l += maxn, r += maxn; l<r; l>>=1, r>>=1) {
if (l&1) re = max(re, s[l++]);
if (r&1) re = max(re, s[--r]);
}
return re;
}
void MO(int p, ll v) {
p += maxn;
for (s[p] = v; p>1; p>>=1) {
s[p>>1] = max(s[p], s[p^1]);
}
}
void clr(){
memset(s, 0, sizeof s);
}
zsk(){ clr();
}
};
ll L[maxn], R[maxn], H[maxn];
int n;
ll lval[maxn], rval[maxn];
zsk hseg;
zsk vseg;
ll getleft(int i, int lp) {
int bg = hseg.QU(lp, i-1+1);
if (bg == 0) return 0;
assert(bg < H[i]);
int hi = *lower_bound(ALL(pos[bg]), lp); // last one in the range
if (L[hi] >= lp) {
return vseg.QU(lp, i-1) + (i-lp) * (ll)(H[i] - bg);
}
ll ret = vseg.QU(hi+1, i);
MX(ret, max(getleft(hi, lp), rval[hi]));
return ret + (i-lp) * (ll)(H[i] - bg);
}
ll getright(int i, int rp) {
int bg = hseg.QU(i+1, rp+1);
if (bg == 0) return 0;
int hi = *prev(upper_bound(ALL(pos[bg]), rp)); // last one in the range
if (R[hi] <= rp) {
return vseg.QU(i+1, rp) + (rp-i) * (ll)(H[i] - bg);
}
ll ret = vseg.QU(i+1, hi);
MX(ret, max(getright(hi, rp), lval[hi]));
return ret + (rp-i) * (ll)(H[i] - bg);
}
std::vector<long long> minimum_costs(std::vector<signed> H, std::vector<signed> QL,
std::vector<signed> QR){
vector<ll> re;
REP(q, SZ(QL)) {
int l = QL[q], r = QR[q];
ll rt = -1;
for (int c = l; c<=r; ++c) {
ll rr = 0;
ll mx = 0;
for (int j = c; j>=l; --j) {
MX(mx, (ll)H[j]); rr += mx;
}
mx = H[c];
for (int j = c+1; j<=r; ++j) {
MX(mx, (ll)H[j]); rr += mx;
}
if (rt == -1 || rr < rt) rt = rr;
}
re.pb(rt);
}
return re;
}
std::vector<long long> minimum_costss(std::vector<signed> _H, std::vector<signed> QL,
std::vector<signed> QR) {
vseg.clr();
hseg.clr();
REP1(i,20) pos[i].clear();
memset(lval,0, sizeof lval);
memset(rval,0, sizeof rval);
n = SZ(_H);
H[0] = H[n+1] = 1000000001;
vector<int> hei;
hei.pb(0);
REP1(i,n) {
H[i] = _H[i-1];
pos[H[i]].pb(i);
while (H[hei.back()] < H[i]) {
hei.pop_back();
}
L[i] = hei.back()+1;
hei.pb(i);
}
REP(i, n+2) hseg.MO(i,H[i]);
hei.clear(); hei.pb(n+1);
for (int i = n; i>=1; --i) {
while (H[hei.back()] < H[i]) {
hei.pop_back();
}
R[i] = hei.back()-1;
hei.pb(i);
}
REP1(i,n) {
bug(i, L[i], R[i]);
}
for (int th = 1; th<=20; ++th) {
// town hall? no. target height :D
REP1(i,n) {
if (H[i] == th) {
lval[i] = getleft(i, L[i]);
rval[i] = getright(i, R[i]);
bug(i, lval[i], rval[i]);
vseg.MO(i, max(lval[i], rval[i]));
}
}
}
vector<ll> ans(SZ(QL));
REP(tat, SZ(QL)) {
int ql = QL[tat], qr = QR[tat];
++ql; ++qr;
int bg = hseg.QU(ql, qr+1);
bug(bg);
int a = *lower_bound(ALL(pos[bg]), ql);
int b = *prev(upper_bound(ALL(pos[bg]), qr));
assert(ql >= L[a]);
assert(qr <= R[b]);
bug(bg, a,b);
ll ret = vseg.QU(a+1, b);
MX(ret, getleft(a, ql));
MX(ret, getright(b, qr));
if (a!=b) {
MX(ret, rval[a]);
MX(ret, lval[b]);
}
bug(ret);
ans[tat] = (qr-ql+1) * bg - ret;
}
return ans;
}
//signed main(){
// int n; cin>>n;
// vector<int> h;
// REP(i,n) h.pb(rand()%5+1);
//
//}
/*
6 3
1 2 1 1 2 1
0 5
1 2
2 4
*/
