#include "meetings.h"
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef pair<ll, ll> pii;
typedef vector<pii> vpii;
typedef vector<vpii> vvpii;
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
const ll INF = 1LL << 60;
int N, Q;
// minsegmenttree
struct segtree
{
vector<ll> arr;
int size;
const ll NEUTRAL = INF;
void init(vi &H)
{
size = 1;
while (size < sz(H))
size *= 2;
arr.resize(2 * size);
for (int i = 0; i < sz(H); ++i)
arr[i + size] = H[i];
for (int i = size - 1; i > 0; --i)
arr[i] = min(arr[2 * i], arr[2 * i + 1]);
}
ll query(int l, int r) { return query(l, r, 1, 0, size); }
ll query(int l, int r, int x, int lx, int rx)
{
if (l <= lx && rx <= r)
return arr[x];
if (r <= lx || rx <= l)
return NEUTRAL;
int m = (lx + rx) / 2;
ll a = query(l, r, 2 * x, lx, m);
ll b = query(l, r, 2 * x + 1, m, rx);
return min(a, b);
}
};
segtree seg[21];
vi occ[21];
segtree segmax;
segtree segmin;
map<ll, ll> cache;
ll query(int l, int r)
{
ll hash = l * (N + 3) + r;
if (cache.find(hash) != cache.end())
return cache[hash];
if (r - l <= 0)
return INF;
ll maxheight = -segmax.query(l, r);
ll minheight = segmin.query(l, r);
if (minheight == maxheight)
return (r - l) * minheight;
int firstOcc = *lower_bound(all(occ[maxheight]), l);
int lastOcc = *(--lower_bound(all(occ[maxheight]), r));
ll ans = INF;
ll tmp;
tmp = query(l, firstOcc);
if (tmp != INF)
ans = min(ans, (r - firstOcc) * maxheight + tmp);
tmp = query(lastOcc + 1, r);
if (tmp != INF)
ans = min(ans, (lastOcc + 1 - l) * maxheight + tmp);
tmp = seg[maxheight - 1].query(firstOcc + 1, lastOcc);
if (tmp != INF)
ans = min(ans, (r - l) * maxheight + tmp);
cache[hash] = ans;
return ans;
}
vi minimum_costs(std::vector<int> H, std::vector<int> L,
std::vector<int> R)
{
N = sz(H);
Q = L.size();
vi dummy(N, INF);
seg[0].init(dummy);
for (int h = 1; h <= 20; ++h)
{
dummy.assign(N, INF);
int l = 0;
int i = 0;
for (; i < N; ++i)
{
if (H[i] > h)
{
if (i > l)
{
ll tmp = (i - l) * h + min(0LL, seg[h - 1].query(l, i)) - (i - l) * (h + 1);
for (int j = l; j < i; ++j)
dummy[j] = tmp;
}
l = i + 1;
}
if (H[i] >= h)
occ[h].push_back(i);
}
if (i > l)
{
ll tmp = (i - l) * h + min(0LL, seg[h - 1].query(l, i)) - (i - l) * (h + 1);
for (int j = l; j < i; ++j)
dummy[j] = tmp;
}
seg[h].init(dummy);
}
for (int i = 0; i < N; ++i)
dummy[i] = -H[i];
segmax.init(dummy);
for (int i = 0; i < N; ++i)
dummy[i] = H[i];
segmin.init(dummy);
vi ans(Q);
for (int j = 0; j < Q; ++j)
{
ans[j] = query(L[j], R[j] + 1);
}
return ans;
}
