#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
struct segment_tree{
int L[800000], R[800000], n;
int t[2100000], T[2100000], root;
long long a[2100000], b[2100000], c[2100000], A[2100000], B[2100000], C[2100000], S[800000];
vector<pair<int, pair<int, int>>> Q[800000];
stack<int> s;
queue<int> q;
void init(int N, int M, vector<int> H, vector<int> X, vector<int> Y){
n = N;
for(int i = 0; i < N; i++)q.push(H[i]);
create_tree(1, 1, N);
for(int i = 0; i < N; i++){
while(!s.empty() && H[s.top()] < H[i]){
int h = s.top();
s.pop();
if(!s.empty() && H[s.top()] < H[i])R[s.top()+1] = h+1;
else L[i+1] = h+1;
}
s.push(i);
}
while(!s.empty()){
int h = s.top();
s.pop();
if(!s.empty())R[s.top()+1] = h+1;
else root = h+1;
}
for(int i = 0; i < M; i++)Q[find_root(X[i], Y[i])].push_back(make_pair(i, make_pair(X[i]+1, Y[i]+1)));
}
void create_tree(int N, int l, int r){
if(l == r){
t[N] = q.front();
T[N] = r;
a[N] = q.front();
A[N] = q.front();
q.pop();
return;
}
create_tree(2*N, l, (l+r)/2);
create_tree(2*N+1, (l+r)/2+1, r);
a[N] = a[2*N];
A[N] = A[2*N+1];
t[N] = max(t[2*N], t[2*N+1]);
T[N] = t[N]==t[2*N]?T[2*N]:T[2*N+1];
}
int get_maximum(int N, int x, int y, int *z, int l, int r){
if(x > r || y < l)return 0;
if(x <= l && y >= r){
if(t[N] > *z){
*z = t[N];
return T[N];
}
return 0;
}
int X = get_maximum(2*N, x, y, z, l, (l+r)/2);
int h = *z;
int Y = get_maximum(2*N+1, x, y, z, (l+r)/2+1, r);
if(h >= *z)return X;
return Y;
}
int find_root(int x, int y){
int z = 0;
return get_maximum(1, x+1, y+1, &z, 1, n);
}
void lazy_left(int N, int l, int r){
if(l==r){
b[N]=0;
c[N]=0;
return;
}
if(b[N]){
b[2*N] = b[N];
b[2*N+1] = b[N];
a[2*N] = a[N];
a[2*N+1] = a[N] + b[N]*((r-l)/2+1);
b[N] = 0;
c[N] = 0;
}
a[2*N] += c[N];
c[2*N] += c[N];
a[2*N+1] += c[N];
c[2*N+1] += c[N];
c[N] = 0;
}
void lazy_right(int N, int l, int r){
if(l==r){
B[N]=0;
C[N]=0;
return;
}
if(B[N]){
B[2*N] = B[N];
B[2*N+1] = B[N];
A[2*N] = A[N] + B[N]*((r-l+1)/2);
A[2*N+1] = A[N];
B[N] = 0;
C[N] = 0;
}
A[2*N] += C[N];
C[2*N] += C[N];
A[2*N+1] += C[N];
C[2*N+1] += C[N];
C[N] = 0;
}
long long get_left(int N, int x, int l, int r){
if(b[N])return a[N]+b[N]*(x-l);
if(l == r)return a[N];
lazy_left(N, l, r);
if(x > (l+r)/2)return get_left(2*N+1, x, (l+r)/2+1, r);
return get_left(2*N, x, l, (l+r)/2);
}
long long get_right(int N, int x, int l, int r){
if(B[N])return A[N]+B[N]*(r-x);
if(l == r)return A[N];
lazy_right(N, l, r);
if(x > (l+r)/2)return get_right(2*N+1, x, (l+r)/2+1, r);
return get_right(2*N, x, l, (l+r)/2);
}
void add_left(int N, int x, int y, long long z, int l, int r){
if(x > r || y < l)return;
if(x <= l && y >= r){
c[N] += z;
a[N] += z;
return;
}
lazy_left(N, l, r);
add_left(2*N, x, y, z, l, (l+r)/2);
add_left(2*N+1, x, y, z, (l+r)/2+1, r);
}
void add_right(int N, int x, int y, long long z, int l, int r){
if(x > r || y < l)return;
if(x <= l && y >= r){
C[N] += z;
A[N] += z;
return;
}
lazy_right(N, l, r);
add_right(2*N, x, y, z, l, (l+r)/2);
add_right(2*N+1, x, y, z, (l+r)/2+1, r);
}
void set_left(int N, int x, int y, long long z, long long Z, int l, int r){
if(x > r || y < l)return;
if(x <= l && y >= r){
a[N] = z+Z*(l-x);
b[N] = Z;
return;
}
lazy_left(N, l, r);
set_left(2*N, x, y, z, Z, l, (l+r)/2);
set_left(2*N+1, x, y, z, Z, (l+r)/2+1, r);
}
void set_right(int N, int x, int y, long long z, long long Z, int l, int r){
if(x > r || y < l)return;
if(x <= l && y >= r){
A[N] = z+Z*(y-r);
B[N] = Z;
return;
}
lazy_right(N, l, r);
set_right(2*N, x, y, z, Z, l, (l+r)/2);
set_right(2*N+1, x, y, z, Z, (l+r)/2+1, r);
}
int find_left(int N, int x, int y, long long z, long long Z, int l, int r){
lazy_left(N, l, r);
if(x <= l){
if(Z * (l-x+1) - a[N] > z)return 0;
if(l == r)return r;
int k = find_left(2*N+1, x, y, z, Z, (l+r)/2+1, r);
if(k)return k;
return find_left(2*N, x, y, z, Z, l, (l+r)/2);
}
if(x > (l+r)/2)return find_left(2*N+1, x, y, z, Z, (l+r)/2+1, r);
if(y < (l+r)/2+1)return find_left(2*N, x, y, z, Z, l, (l+r)/2);
int k = find_left(2*N+1, x, y, z, Z, (l+r)/2+1, r);
if(k)return k;
return find_left(2*N, x, y, z, Z, l, (l+r)/2);
}
int find_right(int N, int x, int y, long long z, long long Z, int l, int r){
lazy_right(N, l, r);
if(y >= r){
if(Z * (y-r+1) - A[N] > z)return 0;
if(l == r)return r;
int k = find_right(2*N, x, y, z, Z, l, (l+r)/2);
if(k)return k;
return find_right(2*N+1, x, y, z, Z, (l+r)/2+1, r);
}
if(x > (l+r)/2)return find_right(2*N+1, x, y, z, Z, (l+r)/2+1, r);
if(y < (l+r)/2+1)return find_right(2*N, x, y, z, Z, l, (l+r)/2);
int k = find_right(2*N, x, y, z, Z, l, (l+r)/2);
if(k)return k;
return find_right(2*N+1, x, y, z, Z, (l+r)/2+1, r);
}
void merge(int N, int l, int r){
if(L[N])merge(L[N], l, N-1);
if(R[N])merge(R[N], N+1, r);
long long X = get_left(1, r, 1, n);
long long Y = get_right(1, l, 1, n);
int Z = 0;
get_maximum(1, N, N, &Z, 1, n);
for(int i = 0; i < Q[N].size(); i++){
if(Q[N][i].second.first == N && Q[N][i].second.second == N){
S[Q[N][i].first] = Z;
continue;
}
if(Q[N][i].second.first == N){
S[Q[N][i].first] = Z+get_left(1, Q[N][i].second.second, 1, n);
continue;
}
if(Q[N][i].second.second == N){
S[Q[N][i].first] = Z+get_right(1, Q[N][i].second.first, 1, n);
continue;
}
S[Q[N][i].first] = Z*(Q[N][i].second.second-Q[N][i].second.first+1)-max(Z*(N-Q[N][i].second.first)-get_right(1, Q[N][i].second.first, 1, n), Z*(Q[N][i].second.second-N)-get_left(1, Q[N][i].second.second, 1, n));
}
if(l < N)add_left(1, N, N, Y, 1, n);
if(r > N)add_right(1, N, N, X, 1, n);
if(!L[N] && !R[N])return;
if(!L[N]){
add_left(1, N+1, r, Z, 1, n);
return;
}
if(!R[N]){
add_right(1, l, N-1, Z, 1, n);
return;
}
int z;
z = find_left(1, N+1, r, 1LL*Z*(N-l)-Y, Z, 1,n);
if(z){
set_left(1, N+1, z, Y+Z*2, Z, 1, n);
if(z<r)add_left(1, z+1, r, Z*(N-l+1), 1, n);
}
else add_left(1, N+1, r, Z*(N-l+1), 1, n);
z = find_right(1, l, N-1, 1LL*Z*(r-N)-X, Z, 1, n);
if(z){
set_right(1, z, N-1, X+Z*2, Z, 1, n);
if(z>l)add_right(1, l, z-1, Z*(N-l+1), 1, n);
}
else add_right(1, l, N-1, Z*(N-l+1), 1, n);
}
} A;
vector<long long> minimum_costs(vector<int> H, vector<int> L,vector<int> R) {
int N = H.size();
int Q = R.size();
A.init(N, Q, H, L, R);
A.merge(A.root, 1, A.n);
vector<long long> Z;
return Z;
}
