#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
#define For(i, l, r) for (auto i = (l); i < (r); i++)
#define ForE(i, l, r) for (auto i = (l); i <= (r); i++)
#define FordE(i, l, r) for (auto i = (l); i >= (r); i--)
#define isz(a) ((signed)a.size())
using ll = long long;
struct query{
int l, r;
};
const int N = 750'000 + 5;
int n, q;
int a[N];
query b[N];
ll ans[N];
namespace subtask12{
bool check(){
return n <= 5000 and q <= 5000;
}
struct monotonic_stack{
vector <pair <int, int>> st;
ll sum;
monotonic_stack(){
st.clear();
sum = 0;
}
void insert(int x){
int len = 1;
while (not st.empty() and st.back().first <= x){
len += st.back().second;
sum -= (ll)st.back().first * st.back().second;
st.pop_back();
}
st.emplace_back(x, len);
sum += (ll)x * len;
}
};
ll tans[N];
vector <ll> solve(){
For(iq, 0, q){
auto &[l, r] = b[iq];
ForE(i, l, r){
tans[i] = -a[i];
}
monotonic_stack st;
ForE(i, l, r){
st.insert(a[i]);
tans[i] += st.sum;
}
st = monotonic_stack();
FordE(i, r, l){
st.insert(a[i]);
tans[i] += st.sum;
}
ans[iq] = *min_element(tans + l, tans + r + 1);
}
return vector <ll>(ans, ans + q);
}
}
namespace subtask3{
bool check(){
return n <= 100'000 and *max_element(a, a + n) <= 2;
}
const int N = 1e5 + 5, LN = 17;
vector <int> pos2;
int delta[N];
int sptb[LN][N];
int query(int l, int r){
int j = __lg(r - l + 1);
return max(sptb[j][l], sptb[j][r - (1 << j) + 1]);
}
vector <ll> solve(){
pos2.emplace_back(-1);
For(i, 0, n){
if (a[i] == 2){
pos2.emplace_back(i);
}
}
pos2.emplace_back(n);
For(i, 0, n){
if (a[i] == 2){
delta[i] = 0;
}
else{
auto itr = --upper_bound(pos2.begin(), pos2.end(), i);
delta[i] += i - *itr;
itr++;
delta[i] += *itr - i;
}
}
For(i, 0, n){
sptb[0][i] = delta[i];
}
For(j, 1, LN){
ForE(i, 0, n - (1 << j)){
sptb[j][i] = max(sptb[j - 1][i], sptb[j - 1][i + (1 << (j - 1))]);
}
}
For(iq, 0, q){
auto &[l, r] = b[iq];
auto tl = *lower_bound(pos2.begin(), pos2.end(), l);
auto tr = *(--upper_bound(pos2.begin(), pos2.end(), r));
if (tl > r){
ans[iq] = r - l + 1;
continue;
}
ans[iq] = 2 * (r - l + 1) - max({tl - l, r - tr, query(tl, tr)});
}
return vector <ll>(ans, ans + q);
}
}
vector <ll> minimum_costs(vector <int> _a, vector <int> _l, vector <int> _r){
n = isz(_a);
q = isz(_l);
For(i, 0, n){
a[i] = _a[i];
}
For(i, 0, q){
auto l = _l[i], r = _r[i];
b[i] = query{l, r};
}
if (subtask12::check()){
return subtask12::solve();
}
if (subtask3::check()){
return subtask3::solve();
}
return {};
}
