#include <bits/stdc++.h>
#include "weirdtree.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
int N, h[300000];
struct Node {
int max, max2, maxco, max2co;
ll sum;
}seg[1048576];
int lazy[1048576];
void merge(Node &ret, Node &l, Node &r) {
if (l.max > r.max) {
ret.max = l.max;
ret.maxco = l.maxco;
if (l.max2 >= r.max) {
ret.max2 = l.max2;
ret.max2co = l.max2co;
if (l.max2 == r.max) ret.max2co += r.maxco;
}
else {
ret.max2 = r.max;
ret.max2co = r.maxco;
}
}
else if (l.max < r.max) {
ret.max = r.max;
ret.maxco = r.maxco;
if (l.max >= r.max2) {
ret.max2 = l.max;
ret.max2co = l.maxco;
if (l.max == r.max2) ret.max2co += r.max2co;
}
else {
ret.max2 = r.max2;
ret.max2co = r.max2co;
}
}
else {
ret.max = l.max;
ret.maxco = l.maxco + r.maxco;
if (l.max2 >= r.max2) {
ret.max2 = l.max2;
ret.max2co = l.max2co;
if (l.max2 == r.max2) ret.max2co += r.max2co;
}
else {
ret.max2 = r.max2;
ret.max2co = r.max2co;
}
}
ret.sum = l.sum + r.sum;
}
void init(int t1, int t2, int idx) {
lazy[idx] = 0;
if (t1 == t2) {
seg[idx].max = seg[idx].sum = h[t1];
seg[idx].max2 = -1;
seg[idx].maxco = 1;
seg[idx].max2co = 0;
return;
}
int mid = (t1 + t2) >> 1;
init(t1, mid, idx << 1);
init(mid + 1, t2, idx << 1 | 1);
merge(seg[idx], seg[idx << 1], seg[idx << 1 | 1]);
}
void dolazy(bool push, int idx) {
if (push) {
if (seg[idx << 1].max - lazy[idx << 1] == seg[idx].max) lazy[idx << 1] += lazy[idx];
if (seg[idx << 1 | 1].max - lazy[idx << 1 | 1] == seg[idx].max) lazy[idx << 1 | 1] += lazy[idx];
}
seg[idx].max -= lazy[idx];
seg[idx].sum -= (ll)lazy[idx] * seg[idx].maxco;
lazy[idx] = 0;
}
void mupdate(int t1, int t2, int q, int val, int idx) {
dolazy(t1 < t2, idx);
if (q < t1 || t2 < q) return;
if (t1 == t2) {
seg[idx].max = seg[idx].sum = val;
seg[idx].max2 = -1;
seg[idx].maxco = 1;
seg[idx].max2co = 0;
return;
}
int mid = (t1 + t2) >> 1;
mupdate(t1, mid, q, val, idx << 1);
mupdate(mid + 1, t2, q, val, idx << 1 | 1);
merge(seg[idx], seg[idx << 1], seg[idx << 1 | 1]);
}
Node query(int t1, int t2, int q1, int q2, int idx) {
dolazy(t1 < t2, idx);
if (q1 <= t1 && t2 <= q2) return seg[idx];
int mid = (t1 + t2) >> 1;
if (q2 <= mid) return query(t1, mid, q1, q2, idx << 1);
if (mid + 1 <= q1) return query(mid + 1, t2, q1, q2, idx << 1 | 1);
Node ret, l = query(t1, mid, q1, q2, idx << 1), r = query(mid + 1, t2, q1, q2, idx << 1 | 1);
merge(ret, l, r);
return ret;
}
void cupdate(int t1, int t2, int q1, int q2, int& lco, int val, int idx) {
dolazy(t1 < t2, idx);
if (q2 < t1 || t2 < q1 || !lco || seg[idx].max <= val) return;
if (q1 <= t1 && t2 <= q2 && seg[idx].max2 < val && seg[idx].maxco <= lco) {
lco -= seg[idx].maxco;
lazy[idx] = seg[idx].max - val;
dolazy(t1 < t2, idx);
return;
}
if (t1 == t2) {
lco--;
seg[idx].max = seg[idx].sum = val;
seg[idx].max2 = -1;
seg[idx].maxco = 1;
seg[idx].max2co = 0;
return;
}
int mid = (t1 + t2) >> 1;
cupdate(t1, mid, q1, q2, lco, val, idx << 1);
cupdate(mid + 1, t2, q1, q2, lco, val, idx << 1 | 1);
merge(seg[idx], seg[idx << 1], seg[idx << 1 | 1]);
}
void initialise(int Nin, int Q, int hin[]) {
N = Nin;
for (int i = 0; i < N; i++) h[i] = hin[i];
init(0, N - 1, 1);
}
void cut(int l, int r, int k) {
l--;
r--;
while (k) {
Node qval = query(0, N - 1, l, r, 1);
if (!qval.max) break;
if (qval.maxco > k) {
cupdate(0, N - 1, l, r, k, qval.max - 1, 1);
assert(!k);
break;
}
else {
int cutlv = min(k / qval.maxco, qval.max - max(qval.max2, 0));
if (!cutlv) break;
k -= cutlv * qval.maxco;
cupdate(0, N - 1, l, r, qval.maxco, qval.max - cutlv, 1);
assert(!qval.maxco);
}
}
}
void magic(int i, int x) {
mupdate(0, N - 1, --i, x, 1);
}
ll inspect(int l, int r) {
inspect(l, r);
return query(0, N - 1, --l, --r, 1).sum;
}
/*
int hinin[6] = {1, 2, 3, 1, 2, 3};
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
initialise(6, 10, hinin);
cut(1, 6, 3);
cout << inspect(1, 6) << '\n';
cut(1, 3, 3);
cout << inspect(1, 6) << '\n';
cut(1, 3, 1000);
cout << inspect(1, 6) << '\n';
//for (int i = 0; i < 6; i++) cout << query(0, 5, i, i, 1).sum << ' ';
//cout << '\n';
magic(1, 1000);
cout << inspect(1, 6) << '\n';
cut(1, 3, 999);
cout << inspect(1, 5) << '\n';
}
*/
