#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define all(x) (x).begin(),(x).end()
typedef long long ll;
typedef pair<int,int> pi;
typedef pair<ll,ll> pl;
const int N = 1e5+5;
const ll INF = 1e18+5;
const int MOD = 1e9+7;
int A[N],seg[4*N];
void build(int s, int e, int idx){
if(s==e){
seg[idx] = A[s];
return;
}
int mid = (s+e)/2;
build(s,mid,idx*2);
build(mid+1,e,idx*2+1);
seg[idx] = max(seg[idx*2],seg[idx*2+1]);
}
int query(int s, int e, int idx, int qs, int qe){
if(qs<=s && e<=qe)return seg[idx];
if(s > qe || e < qs)return 0;
int mid = (s+e)/2;
return max(query(s,mid,idx*2,qs,qe),query(mid+1,e,idx*2+1,qs,qe));
}
vector<long long> minimum_costs(vector<int> arr, vector<int> L, vector<int> R) {
int n = arr.size();
int q = L.size();
int i,j,k;
vector<ll> ans(q);
// good i is always local minima
//if(i-1 >= x && arr[i-1] < arr[i] || i+1 <= y && arr[i+1] < arr[i])continue;
int cnt = 0;
for(i=0;i<n;i++){
if(arr[i] == 2){
int temp = cnt;
int j = i-1;
while(temp--){
A[j] = cnt;
j--;
}
cnt = 0;
A[i] = 0;
}
else
cnt++;
}
int temp = cnt;
j = i-1;
while(temp--){
A[j] = cnt;
j--;
}
cnt = 0;
A[i] = 0;
for(i=0;i<n;i++){
cerr<<A[i]<<" ";
}cerr<<endl;
build(0,n-1,1);
for(k=0;k<q;k++){
int x = L[k];
int y = R[k];
ll res = (y-x+1)*2 - query(0,n-1,1,x,y);
ans[k] = res;
}
return ans;
}
