#include <bits/stdc++.h>
#include "weirdtree.h"
using namespace std;
using ll = long long;
using ld = long double;
#define fi first
#define se second
#define vi vector<int>
#define vll vector<long long>
#define pii pair<int, int>
#define pll pair<long long, long long>
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
mt19937_64 rng64(chrono::high_resolution_clock::now().time_since_epoch().count());
inline int rand(int l,int r){return uniform_int_distribution<int>(l, r)(rng);}
inline ll rand(ll l,ll r){return uniform_int_distribution<ll>(l, r)(rng64);}
#ifdef DEBUG
auto&operator<<(auto&o,pair<auto,auto>p){return o<<"("<<p.first<<", "<<p.second<<")";}
auto operator<<(auto&o,auto x)->decltype(x.end(),o){o<<"{";int i=0;for(auto e:x)o<<","+!i++<<e;return o<<"}";}
#define debug(X...)cerr<<"["#X"]: ",[](auto...$){((cerr<<$<<"; "),...)<<endl;}(X)
#else
#define debug(...){}
#endif
struct custom_hash {
static uint64_t splitmix64(uint64_t x) {
x += 0x9e3779b97f4a7c15;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
return x ^ (x >> 31);
}
size_t operator()(uint64_t x) const {
static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
return splitmix64(x + FIXED_RANDOM);
}
};
struct pair_hash{
size_t operator()(const pair<int,int>&x)const{
return hash<long long>()(((long long)x.first)^(((long long)x.second)<<32));
}
};
struct Node{
ll mx1, mx2, f1, sum;
Node(){
mx1 = mx2 = f1 = sum = 0LL;
}
Node(ll a){
mx1 = sum = a;
f1 = 1LL;
mx2 = 0LL;
}
Node(ll a, ll b, ll c, ll d){
mx1 = a;
mx2 = b;
f1 = c;
sum = d;
}
Node operator+(const Node& other) const{
if(mx1 == other.mx1){
return Node(mx1, max(mx2, other.mx2), f1 + other.f1, sum + other.sum);
}else if(mx1 > other.mx1){
return Node(mx1, max(mx2, other.mx1), f1, sum + other.sum);
}else{
return Node(other.mx1, max(mx1, other.mx2), other.f1, sum + other.sum);
}
}
};
const int BASE = (1 << 19);
Node tree[2 * BASE + 7];
ll H[BASE];
int n, q;
void upd(int i, ll x){
i += BASE;
tree[i] = Node(x);
i /= 2;
while(i > 0){
tree[i] = tree[2 * i] + tree[2 * i + 1];
i /= 2;
}
}
ll query(int v, int l, int p, int a, int b){
if(p < a || b < l){
return 0LL;
}
if(a <= l && p <= b){
return tree[v].sum;
}
int mid = (l + p) / 2;
ll ret = (ll)query(2 * v, l, mid, a, b) + query(2 * v + 1, mid + 1, p, a, b);
tree[v] = tree[2 * v] + tree[2 * v + 1];
return ret;
}
void initialise(int N, int Q, int h[]) {
n = N;
q = Q;
for(int i = 1; i <= n; i++){
H[i] = h[i];
tree[i + BASE] = Node(H[i]);
}
for(int i = BASE; i >= 1; i--){
tree[i] = tree[2 * i] + tree[2 * i + 1];
}
}
Node join(int v, int l, int p, int a, int b){
if(p < a || b < l){
return Node();
}
if(a <= l && p <= b){
return tree[v];
}
int mid = (l + p) / 2;
return join(2 * v, l, mid, a, b) + join(2 * v + 1, mid + 1, p, a, b);
}
ll v1,c1, v2, c2,mx1,mx2;
void changeAll(int v, int l, int p, int a, int b){
if(p < a || b < l){
return;
}
if(a <= l && p <= b){
if(tree[v].mx1 < mx1){
return;
}
if(l == p){
tree[v].mx1 = mx2;
tree[v].sum -= (tree[v].f1 * (mx1 - mx2));
return;
}
}
int mid = (l + p) / 2;
changeAll(2 * v, l, mid ,a, b);
changeAll(2 * v + 1, mid + 1, p, a, b);
tree[v] = tree[2 * v] + tree[2 * v + 1];
}
pii used = mp(0, 0);
void change(int v, int l, int p, int a, int b){
if(p < a || b < l || tree[v].mx1 < mx1){
return;
}
if(a <= l && p <= b && l == p){
if(used.fi < c1){
tree[v].mx1 = v1;
used.fi++;
tree[v].sum -= (tree[v].f1 * (mx1 - v1));
}else{
tree[v].mx1 = v2;
used.se++;
tree[v].sum -= (tree[v].f1 * (mx1 - v2));
}
return;
}
int mid = (l + p) / 2;
change(2 * v, l, mid, a, b);
change(2 * v + 1, mid + 1, p, a, b);
tree[v] = tree[2 * v] + tree[2 * v + 1];
}
void cut(int l, int r, int k) {
//cout << "-----\n";
Node curr;
while(k){
curr = join(1, 0, BASE - 1, l, r);
/*for(int i = 1; i <= 6; i++){
cout << tree[i + BASE].mx1 << ' ';
}
cout << '\n';
cout << curr.mx1 << ' ' << curr.mx2 << ' ' << curr.f1 << '\n';
cout << (ll)(curr.mx1 - curr.mx2) * curr.f1 << ' ' << k << '\n';*/
mx1 = curr.mx1;
mx2 = curr.mx2;
if((ll)(curr.mx1 - curr.mx2) * curr.f1 > k){
v1 = mx1 - (k + curr.f1 - 1) / curr.f1;
v2 = mx1 - k / curr.f1;
c1 = k - curr.f1 * v2;
c2 = curr.f1 - c1;
used = mp(0, 0);
change(1, 0, BASE - 1, l, r);
k = 0;
}else{
k = (ll)k - (ll)(curr.mx1 - curr.mx2) * curr.f1;
changeAll(1, 0, BASE - 1, l, r);
if(curr.mx2 == 0){
k = 0;
}
}
}
}
void magic(int i, int x){
H[i] = x;
upd(i, x);
}
ll inspect(int l, int r) {
return query(1, 0, BASE - 1, l, r);
}
/*int main(){
int h[7] = {0, 1, 2, 3, 1, 2, 3};
initialise(6, 10, h);
cut(1, 6, 3);
//for(int i = 1; i <= 6; i++){
// cout << tree[i + BASE].mx1 << ' ';
//}
//cout << '\n';
cout << inspect(1, 6) << '\n';
cut(1, 3, 3);
cout << inspect(1, 6) << '\n';
cut(1, 3, 1000);
cout << inspect(1, 6) << '\n';
magic(1, 1000);
cout << inspect(1, 6) << '\n';
cut(1, 3, 999);
cout << inspect(1, 5) << '\n';
return 0;
} */
