#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define ss second
#define ff first
#define sz(a) int(a.size())
#define all(a) a.begin(),a.end()
#define mkp make_pair
typedef long double ld;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
const ll inf = 1e18;
const int mod = 1e9+7; //998244353;
const int maxn = 1e5+5,N=1e6;
const int Xg[4] = {1,0,-1,0}, Yg[4] = {0,1,0,-1};
ll modpw(ll a,ll e) {if(e==0)return 1;ll x=modpw(a*a%mod,e>>1);return e&1?x*a%mod:x;}
int T[3][4*N];
vi arr[3];
ll p[maxn];
ll jog[maxn];
stack<pii>s;
vector<pii> v;
void build(int l,int r,int nd,int tp){
if(l==r){
T[tp][nd]=arr[tp][l];
return;
}
build(l,(l+r)/2,nd*2,tp);
build((l+r)/2+1,r,nd*2+1,tp);
T[tp][nd]=max(T[tp][nd*2],T[tp][nd*2+1]);
}
int tap(int a,int b,int l,int r,int nd,int tp){
if(r < a or l > b) return 0;
if(l >= a and r <= b) return T[tp][nd];
return max(tap(a,b,l,(l+r)/2,nd*2,tp),tap(a,b,(l+r)/2+1,r,nd*2+1,tp));
}
vll minimum_costs(vi H, vi L,vi R) {
int Q=sz(L); vll C;
if(Q<1e4){
int cep[maxn],sag[maxn];
memset(cep,0,sizeof(cep));
memset(sag,0,sizeof(sag));
for(int i = 0;i < Q;i++){
memset(jog,0,sizeof(jog));
memset(cep,0,sizeof(cep));
memset(sag,0,sizeof(sag));
memset(p,0,sizeof(p));
while(!s.empty()) s.pop();
for(int j = L[i];j <= R[i];j++){
while(!s.empty() and s.top().ss <= H[j]) s.pop();
if(!s.empty()) cep[j]=s.top().ff+1;
else cep[j]=L[i];
s.push({j,H[j]});
}
while(!s.empty()) s.pop();
for(int j = R[i];j >= L[i];j--){
while(!s.empty() and s.top().ss < H[j]) s.pop();
if(!s.empty()) sag[j]=s.top().ff-1;
else sag[j]=R[i];
s.push({j,H[j]});
}
for(int j = L[i];j <= R[i];j++){
ll num=j-cep[j];
ll num1= sag[j]-j;
p[cep[j]] += ((num1+1)*H[j]);
p[j] -= ((num1+1)*H[j]);
p[j+1] += ((num+1)*H[j]);
p[sag[j]+1] -= ((num+1)*H[j]);
jog[j] = (num+num1+1)*H[j];
}
ll ans = inf;
for(int j = L[i];j <= R[i];j++){
if(j) p[j] += p[j-1];
ans = min(ans,p[j]+jog[j]);
}
C.pb(ans);
}
return C;
}
else {
int n = sz(H);
int num=0;
vi v[3];
for(int i = 0;i < n;i++){
if(H[i]==2){
num=0;
}
else num++;
arr[0].pb(num);
if(num==1) v[0].pb(i);
}
build(0,n-1,1,0);
num=0;
for(int i = n-1;i >= 0;i--){
if(H[i]==2){
num=0;
}
else num++;
arr[1].pb(num);
if(num==1) v[1].pb(i);
}
reverse(all(v[1]));
build(0,n-1,1,1);
for(int i = 0;i < Q;i++){
int pos1=lower_bound(all(v[0]),L[i])-v[0].begin();
int pos2=upper_bound(all(v[1]),R[i])-v[1].begin();
pos2--;
int max1=tap(v[0][pos1],R[i],0,n-1,1,0);
int max2=tap(L[i],v[1][pos2],0,n-1,1,1);
C.pb(2*(R[i]-L[i]+1)-max(max1,max2));
}
return C;
}
}
