#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
constexpr int N = 1e7;
struct segtree{
using t = tuple<int,int,int>;
int size = 1; t arr[N] = {t(0,0,0)};
segtree(int n){while(size<n) size*=2;}
void merge(t l, t r, t& result, int lx, int rx, int m) {
if(get<1>(l)==m){
if(get<1>(r)==m) result = t(rx-lx,rx-lx,rx-lx);
else result = t((get<1>(r))+m-lx,(get<1>(r))+m-lx, get<2>(r));
}
else if(get<1>(r)==m) result = t((get<2>(l))+m-lx,(get<2>(l))+m-lx, get<1>(l));
else
result = t(max(max(get<0>(l),get<0>(r)), (get<1>(r))+get<2>(l))
,get<1>(l), get<2>(r));
}
void set(int i, int u){
set(i,u,0,0,size);
}
void set(int i, int u, int x, int lx, int rx){
if(rx-lx==1){
if(u==2) arr[x] = t(0,0,0);
else arr[x] = t(1,1,1);
return;
}
int m = (rx+lx)/2;
if(i<m) set(i,u,2*x+1,lx,m);
else set(i,u,2*x+2,m,rx);
merge(arr[2*x+1],arr[2*x+2],arr[x],lx,rx,m);
}
t goat(int l, int r){
return goat(l,r,0,0,size);
}
t goat(int l, int r, int x, int lx, int rx){
if(rx<=l||lx>=r) return t(0,0,0);
if(rx<=r&&lx>=l) return arr[x];
int m = (rx+lx)/2;
t res;
merge(goat(l,r,2*x+1,lx,m), goat(l,r,2*x+2,m,rx), res,lx,rx,m);
return res;
}
};
std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L,
std::vector<int> R) {
int Q = L.size();
vector<long long> C;
int n = H.size();
segtree sgt(n);
for(int i = 0; i<n; i++) sgt.set(i,H[i]);
for(int i = 0; i<Q; i++){
C.push_back(2*(R[i]-L[i]+1)-get<0>(sgt.goat(L[i], R[i]+1)));
}
return C;
}
