#define ll long long
#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
ll left(ll i)
{
return 2*i;
}
ll right(ll i)
{
return 2*i+1;
}
ll s[10001];
ll query(ll i, ll a, ll b, ll l, ll r)
{
if(l <= a && b <= r)
{
return s[i];
}
if(r < a || b < l)
{
return 0;
}
ll mid = (a+b)/2;
return max(query(left(i), a, mid, l, r), query(right(i), mid+1, b, l, r));
}
std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L, std::vector<int> R)
{
ll n = H.size();
ll segnodes = 1;
while(2*n > segnodes)
{
segnodes *= 2;
}
for(ll i = 0; i <= 10000; i++)
{
s[i] = 0;
}
for(ll i = 0; i < n; i++)
{
s[i+segnodes/2] = H[i];
}
for(ll i = segnodes/2-1; i > 0; i--)
{
s[i] = max(s[left(i)], s[right(i)]);
}
vector<ll> output(0);
for(ll i = 0; i < (ll) L.size(); i++)
{
ll len = R[i]+1-L[i];
//Going from left to right:
vector<ll> pre(len, 0);
for(ll j = 0; j < len; j++)
{
if(H[L[i]+j] >= query(1, 1, segnodes/2, L[i]+1, L[i]+j+1))
{
//No bigger mountain before
pre[j] = (j+1)*(ll) H[j+L[i]];
}
else
{
//Looking for last mountain bigger than this one
ll node = segnodes/2+j+L[i];
ll high = H[j+L[i]];
while(high <= H[j+L[i]])
{
ll par = node/2;
if(node == right(par))
{
high = max(high, s[left(par)]);
}
node = par;
}
node = left(node);
//Go down:
while(left(node) < segnodes)
{
if(s[right(node)] > H[j+L[i]])
{
node = right(node);
}
else
{
node = left(node);
}
}
node -= segnodes/2+L[i];
pre[j] = pre[node] + (j-node)*(ll)(H[j+L[i]]);
}
}
//Going from right to left:
vector<ll> post(len, 0);
for(ll j = len-1; j >= 0; j--)
{
if(H[L[i]+j] >= query(1, 1, segnodes/2, L[i]+j+1, R[i]+1))
{
//No bigger mountain after that one
post[j] = (len-j)*(ll)H[j+L[i]];
}
else
{
//Looking for first mountain bigger than this one
ll node = segnodes/2+j+L[i];
ll high = H[j+L[i]];
while(high <= H[j+L[i]])
{
ll par = node/2;
if(node == left(par))
{
high = max(high, s[right(par)]);
}
node = par;
}
node = right(node);
//Go down:
while(left(node) < segnodes)
{
if(s[left(node)] > H[j+L[i]])
{
node = left(node);
}
else
{
node = right(node);
}
}
node -= segnodes/2+L[i];
post[j] = post[node] + (node-j)*(ll)(H[j+L[i]]);
}
}
output.push_back(numeric_limits<ll>::max()/2);
for(ll j = 0; j < len; j++)
{
output.back() = min(output.back(), (ll) pre[j]+post[j]-(ll)H[L[i]+j]);
}
}
return output;
}
