#include "meetings.h"
#include<iostream>
#include<algorithm>
#include<vector>
#include<cassert>
#include<utility>
using namespace std;
typedef long long ll;
namespace{
int n, q;
vector<ll> vec;
}
struct node{
ll maxi, tag;
node(ll a, ll b){
maxi = a, tag = b;
}
};
struct st{
vector<node> seg;
st(int N){
seg.resize(4 * N + 4, node(0, 0));
}
void push(int l, int r, int ind){
if(l == r) return;
seg[ind * 2].maxi += seg[ind].tag;
seg[ind * 2 + 1].maxi += seg[ind].tag;
seg[ind * 2].tag += seg[ind].tag;
seg[ind * 2 + 1].tag += seg[ind].tag;
seg[ind].tag = 0;
}
void modify(int l, int r, int start, int end, ll val, int ind){
if(r < start || end < l) return;
if(start <= l && r <= end){
seg[ind].maxi += val;
seg[ind].tag += val;
return;
}
int mid = (l + r) >> 1;
push(l, r, ind);
modify(l, mid, start, end, val, ind * 2);
modify(mid + 1, r, start, end, val, ind * 2 + 1);
seg[ind].maxi = max(seg[ind * 2].maxi, seg[ind * 2 + 1].maxi);
}
ll query(int l, int r, int start, int end, int ind){
if(r < start || end < l) return 0;
if(start <= l && r <= end) return seg[ind].maxi;
push(l, r, ind);
int mid = (l + r) >> 1;
return max(query(l, mid, start, end, ind * 2), query(mid + 1, r, start, end, ind * 2 + 1));
}
};
std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L, std::vector<int> R) {
n = H.size();
q = L.size();
vec.resize(n + 1);
for(int i = 1; i <= n; i++) vec[i] = H[i - 1], assert(vec[i] <= 20);
vector<ll> ans(q);
st seg(n);
vector<vector<pair<int, int>>> rngs(21);
for(int i = 1; i < 20; i++){
int curl = -1;
bool flag = 0;
for(int j = 1; j <= n; j++){
if(vec[j] <= i){
if(curl == -1) curl = j;
flag = 1;
}
else{
if(flag){
rngs[i].emplace_back(curl, j - 1);
}
flag = 0;
curl = -1;
}
}
if(curl > 0) rngs[i].emplace_back(curl, n);
}
for(int i = 1; i < 20; i++){
for(auto &[l, r]: rngs[i]){
seg.modify(1, n, l, r, r - l + 1, 1);
}
}
for(int hey = 0; hey < q; hey++){
int l = L[hey] + 1, r = R[hey] + 1;
for(int i = 1; i < 20; i++){
auto iter = lower_bound(rngs[i].begin(), rngs[i].end(), make_pair(l, 0));
if(iter != rngs[i].begin()){
auto &[curl, curr] = (*prev(iter));
if(l <= curr){
seg.modify(1, n, l, curr, -l + curl, 1);
}
}
iter = upper_bound(rngs[i].begin(), rngs[i].end(), make_pair(r, n + 1));
if(iter != rngs[i].begin()){
auto &[curl, curr] = (*prev(iter));
if(curr > r){
seg.modify(1, n, curl, r, -curr + r, 1);
}
}
}
ans[hey] = 20ll * (r - l + 1) - seg.query(1, n, l, r, 1);
for(int i = 1; i < 20; i++){
auto iter = lower_bound(rngs[i].begin(), rngs[i].end(), make_pair(l, 0));
if(iter != rngs[i].begin()){
auto &[curl, curr] = (*prev(iter));
if(l <= curr){
seg.modify(1, n, l, curr, l - curl, 1);
}
}
iter = upper_bound(rngs[i].begin(), rngs[i].end(), make_pair(r, n + 1));
if(iter != rngs[i].begin()){
auto &[curl, curr] = (*prev(iter));
if(curr > r){
seg.modify(1, n, curl, r, curr - r, 1);
}
}
}
}
return ans;
}
// g++ -std=c++17 -Wall -Wextra -Wshadow -fsanitize=undefined -fsanitize=address -o run grader.cpp meetings.cpp
