#include "meetings.h"
using namespace std;
typedef vector<int> vi;
typedef vector<long long> vl;
const int N = 750000, N_ = 1 << 18, A = 20;
const long long INF = 0x3f3f3f3f3f3f3f3fLL;
long long min(long long a, long long b) { return a < b ? a : b; }
long long max(long long a, long long b) { return a > b ? a : b; }
int qu[N]; long long pp[N], qq[N];
int ll_[N][A], rr_[N][A], xx[N], yy[N];
int eval_l(int l, int i) {
int a, x;
x = A * (i - l + 1);
for (a = A - 1; a >= 0; a--)
if (i >= ll_[i][a])
x -= i - max(ll_[i][a], l) + 1;
return x;
}
int eval_r(int r, int i) {
int a, x;
x = A * (r - i);
for (a = A - 1; a >= 0; a--)
if (i <= rr_[i][a])
x -= min(rr_[i][a], r) - i;
return x;
}
int sum[N_ * 2], pref[N_ * 2], n_;
void pul(int i) {
int l = i << 1, r = l | 1;
sum[i] = sum[l] + sum[r];
pref[i] = min(pref[l], sum[l] + pref[r]);
}
void update(int i, int x) {
i += n_;
pref[i] = min(sum[i] = x, 0);
while (i > 1)
pul(i >>= 1);
}
int query(int l, int r) {
int p, q, s;
p = q = s = 0;
for (l += n_, r += n_; l <= r; l >>= 1, r >>= 1) {
if ((l & 1) == 1)
p = min(p, s + pref[l]), s += sum[l], l++;
if ((r & 1) == 0)
q = min(pref[r], sum[r] + q), r--;
}
return min(p, s + q);
}
vl minimum_costs(vi aa, vi ll, vi rr) {
int n = aa.size(), q = ll.size(), h, cnt;
vl ans(q);
if (n <= 5000 && q <= 5000) {
for (h = 0; h < q; h++) {
int l = ll[h], r = rr[h], i;
long long x;
cnt = 0, x = 0;
for (i = l; i <= r; i++) {
x += aa[i];
while (cnt && aa[qu[cnt - 1]] < aa[i]) {
cnt--;
x += (long long) (aa[i] - aa[qu[cnt]]) * (qu[cnt] - (cnt == 0 ? l - 1 : qu[cnt - 1]));
}
qu[cnt++] = i;
pp[i] = x;
}
cnt = 0, x = 0;
for (i = r; i >= l; i--) {
x += aa[i];
while (cnt && aa[qu[cnt - 1]] < aa[i]) {
cnt--;
x += (long long) (aa[i] - aa[qu[cnt]]) * ((cnt == 0 ? r + 1 : qu[cnt - 1]) - qu[cnt]);
}
qu[cnt++] = i;
qq[i] = x;
}
ans[h] = INF;
for (i = l; i <= r; i++)
ans[h] = min(ans[h], pp[i] + qq[i] - aa[i]);
}
} else {
int i, a;
for (i = 0; i < n; i++)
for (a = 0; a < A; a++)
ll_[i][a] = aa[i] > a ? i + 1 : (i == 0 ? 0 : ll_[i - 1][a]);
for (i = n - 1; i >= 0; i--)
for (a = 0; a < A; a++)
rr_[i][a] = aa[i] > a ? i - 1 : (i + 1 == n ? n - 1 : rr_[i + 1][a]);
for (i = 1; i < n; i++)
xx[i] = eval_l(0, i) - eval_l(0, i - 1), yy[i] = eval_r(n - 1, i) - eval_r(n - 1, i - 1);
n_ = 1;
while (n_ < n)
n_ <<= 1;
for (i = 1; i < n; i++)
update(i, xx[i] + yy[i]);
for (h = 0; h < q; h++) {
int l = ll[h], r = rr[h], i_;
i_ = l;
for (a = 0; a < A; a++)
if (i_ < ll_[i][a] + 1) {
i_ = ll_[i][a] + 1;
if (i_ < n)
update(i_, eval_l(l, i_) - eval_l(l, i_ - 1) + eval_r(r, i_) - eval_r(r, i_ - 1));
}
i_ = r;
for (a = 0; a < A; a++)
if (i_ > rr_[i][a] - 1) {
i_ = rr_[i][a] - 1;
if (i_ >= 0)
update(i_ + 1, eval_l(l, i_ + 1) - eval_l(l, i_) + eval_r(r, i_ + 1) - eval_r(r, i_));
}
i_ = l;
for (a = 0; a < A; a++)
if (i_ < ll_[i][a] + 1) {
i_ = ll_[i][a] + 1;
if (i_ < n)
update(i_, xx[i_] + yy[i_]);
}
i_ = r;
for (a = 0; a < A; a++)
if (i_ > rr_[i][a] - 1) {
i_ = rr_[i][a] - 1;
if (i_ >= 0)
update(i_ + 1, xx[i_ + 1] + yy[i_ + 1]);
}
ans[h] = eval_l(l, l) + eval_r(r, l) + (l == r ? 0 : query(l + 1, r));
}
}
return ans;
}
