#include "meetings.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
struct segtree{
struct node{
int l,r;
int vl,vr;
int mx;
};
vector<node> tree;
int size=1;
ll op(ll x,ll y){
return max(x,y);
}
int getnode(int n){
return n+size;
}
void build(vector<int> arr){
while(size< arr.size()) size*=2;
tree.resize(size*2);
for(int i=0; i < size;i++){
tree[i+size].l=i;
tree[i+size].r=min(i,(int)arr.size()-1);
tree[i+size].vl=(arr[i]==1);
tree[i+size].vr=(arr[i]==1);
tree[i+size].mx=(arr[i]==1);
}
for(int i=size-1;i>=1;i--){
tree[i].l=tree[i*2].l;
tree[i].r=tree[i*2+1].r;
if(tree[i*2].vl==tree[i*2].r - tree[i*2].l + 1){
tree[i].vl=tree[i*2].vl+tree[i*2+1].vl;
} else{
tree[i].vl=tree[i*2].vl;
} if(tree[i*2+1].vr==tree[i*2 + 1].r - tree[i*2 + 1].l + 1){
tree[i].vr=tree[i*2+1].vr+tree[i*2].vr;
} else{
tree[i].vr=tree[i*2+1].vr;
}
tree[i].mx=max({tree[i].vl,tree[i].vr,tree[i*2].vr + tree[i*2+1].vl,tree[i*2].mx,tree[i*2+1].mx});
}
}
int getr(int left,int mxr){
int curr=getnode(left);
int val=0;
while(curr && tree[curr].mx==tree[curr].r - tree[curr].l + 1 && tree[curr].r <mxr){
int prev=curr;
curr/=2;
if(tree[curr].l != tree[prev].l){
return tree[prev].vl + getr(tree[prev].r+1, mxr);
}
}
val=min(tree[curr].vl,mxr - left + 1);
return val;
}
int getl(int right,int mxl){
int curr=getnode(right);
int val=0;
while(curr && tree[curr].mx==tree[curr].r - tree[curr].l + 1 && tree[curr].l <mxl){
int prev=curr;
curr/=2;
if(tree[curr].r != tree[prev].r){
return tree[prev].vr + getr(tree[prev].l-1, mxl);
}
}
val=min(tree[curr].vr,right - mxl + 1);
return val;
}
int get(int L,int R,int node,int mxl,int mxr){
if(tree[node].r<L || tree[node].l > R) return 0;
if(tree[node].l >=L && tree[node].r <=R){
if(L== tree[node].l && R==tree[node].r) return tree[node].mx;
if(tree[node].r - tree[node].l + 1 == tree[node].mx){
if(L==tree[node].l) return tree[node].mx + getr(tree[node].r + 1,mxr);
if(R==tree[node].r) return tree[node].mx + getl(tree[node].l - 1,mxl);
return tree[node].mx + getl(tree[node].l - 1,mxl) + getr(tree[node].r + 1,mxr);
} else{
if(L==tree[node].l) return op(tree[node].vr + getr(tree[node].r + 1,mxr),tree[node].mx);
if(R==tree[node].r) return op(tree[node].vl + getl(tree[node].l - 1,mxl),tree[node].mx);
return max({tree[node].mx,tree[node].vl + getl(tree[node].l - 1,mxl),tree[node].vr + getr(tree[node].r + 1,mxr)});
}
}
return op(get(L,R,node*2,mxl,mxr) , get(L,R,node*2+1,mxl,mxr));
}
void out(){
for(node x : tree){
cout << x.mx << ' ';
}
}
};
vector<ll> minimum_costs(vector<int> H, vector<int> L,vector<int> R) {
int q=L.size();
segtree arr;
arr.build(H);
vector<ll> ans(q);
for(int i=0;i<q;i++){
int l=L[i];
int r=R[i];
int curr=arr.get(l,r,1,l,r);
ans[i]=((r-l+1) *2) - curr ;
}
// arr.out();
return ans;
}
// void solve(){
// int n; cin >> n;
// int q; cin >> q;
// vector<int> temp(n);
// vector<int> L(q),R(q);
// for(int i=0; i < n;i++) cin >> temp[i];
// for(int i=0; i < q;i++) cin >> L[i] >> R[i];
// vector<ll> ans=minimum_costs(temp,L,R);
// for(auto c : ans) cout << c << endl;
// }
// int main(){
// ios::sync_with_stdio(false);
// cin.tie(0);
// cout.tie(0);
// int t=1;
// // cin >> t;
// while(t--) solve();
// return 0;
// }
