#include "meetings.h"
#include<bits/stdc++.h>
using namespace std;
/*
namespace {
int read_int() {
int x;
if (scanf("%d", &x) != 1) {
fprintf(stderr, "Error while reading input\n");
exit(1);
}
return x;
}
} // namespace
*/
struct info
{
int l,r,av;
long long outp;
int left_child,right_child;
};
vector<info> tree;
vector<int> inp;
long long build(int node,int l,int r)
{
if(l>r)return 0;
int mx=0;
for(int j=l;j<=r;j++)
mx=max(mx,inp[j]);
vector<int> v={};
for(int j=l;j<=r;j++)
if(inp[j]==mx)v.push_back(j);
int cur=tree.size();
int av=v[v.size()/2];
info me;
me.l=l;
me.r=r;
me.av=av;
tree.push_back(me);
tree[node].left_child=node+1;
long long LHS=build(tree.size(),l,av-1)+1LL*mx*(r-av+1);
tree[node].right_child=tree.size();
long long RHS=build(tree.size(),av+1,r)+1LL*mx*(av-l+1);
tree[node].outp=min(LHS,RHS);
//cout<<l<<" "<<r<<" -> "<<tree[node].outp<<endl;
return min(LHS,RHS);
}
long long query(int node,int l,int r,int lq,int rq)
{
if(l>r||lq>rq)return 0;
if(l==lq&&r==rq)return tree[node].outp;
int av=tree[node].av;
if(rq<av)return query(tree[node].left_child,l,tree[node].av-1,lq,rq);
if(av<lq)return query(tree[node].right_child,tree[node].av+1,r,lq,rq);
long long LHS=query(tree[node].left_child,l,av-1,lq,av-1)+1LL*(rq-av+1)*inp[tree[node].av];
long long RHS=query(tree[node].right_child,av+1,r,av+1,rq)+1LL*(av-lq+1)*inp[tree[node].av];
return min(LHS,RHS);
}
std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L,
std::vector<int> R) {
inp=H;
build(0,0,inp.size()-1);
vector<long long> outp={};
for(int i=0;i<L.size();i++)
outp.push_back(query(0,0,inp.size()-1,L[i],R[i]));
return outp;
}
/*
int main() {
int N = read_int();
int Q = read_int();
std::vector<int> H(N);
for (int i = 0; i < N; ++i) {
H[i] = read_int();
}
std::vector<int> L(Q), R(Q);
for (int j = 0; j < Q; ++j) {
L[j] = read_int();
R[j] = read_int();
}
std::vector<long long> C = minimum_costs(H, L, R);
for (size_t j = 0; j < C.size(); ++j) {
printf("%lld\n", C[j]);
}
return 0;
}
*/
