#include <bits/stdc++.h>
#include "meetings.h"
using ll = long long;
template <class T> using Vec = std::vector<T>;
constexpr ll INF = std::numeric_limits<ll>::max();
template <class T> void setmin(T& x, const T& y) {
if (x > y) {
x = y;
}
}
template <class T> void setmax(T& x, const T& y) {
if (x < y) {
x = y;
}
}
struct RMQ {
Vec<Vec<int>> table;
RMQ(const Vec<int>& vec) {
const int n = (int) vec.size();
int k = 0;
while ((1 << k) <= n) {
k += 1;
}
table.resize(k);
table[0] = vec;
for (int h = 0; h < k - 1; ++h) {
const int len = n - (1 << (h + 1)) + 1;
table[h + 1].resize(len);
for (int i = 0; i < len; ++i) {
table[h + 1][i] = std::max(table[h][i], table[h][i + (1 << h)]);
}
}
}
int fold(const int l, const int r) {
if (l >= r) {
return std::numeric_limits<int>::min();
}
const int h = 31 - __builtin_clz(r - l);
return std::max(table[h][l], table[h][r - (1 << h)]);
}
};
Vec<ll> minimum_costs(Vec<int> H, Vec<int> L, Vec<int> R) {
const int N = (int) H.size();
const int Q = (int) L.size();
if (N <= 5000) {
Vec<Vec<int>> cost(N, Vec<int>(N));
for (int i = 0; i < N; ++i) {
int max = H[i];
cost[i][i] = max;
for (int j = i - 1; j >= 0; --j) {
setmax(max, H[j]);
cost[i][j] = max;
}
max = H[i];
for (int j = i + 1; j < N; ++j) {
setmax(max, H[j]);
cost[i][j] = max;
}
}
Vec<Vec<ll>> sum(N, Vec<ll>(N + 1));
for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; ++j) {
sum[i][j + 1] = sum[i][j] + cost[i][j];
}
}
Vec<ll> ret(Q, INF);
for (int i = 0; i < Q; ++i) {
const int l = L[i];
const int r = R[i] + 1;
for (int j = l; j < r; ++j) {
setmin(ret[i], sum[j][r] - sum[j][l]);
}
}
return ret;
} else {
Vec<std::pair<int, int>> one;
{
int l = 0;
while (l < N) {
if (H[l] == 2) {
l += 1;
continue;
}
int r = l;
while (r < N and H[r] == 1) {
r += 1;
}
one.emplace_back(l, r);
l = r;
}
}
const int M = (int) one.size();
Vec<int> len(M + 1);
for (int i = 0; i < M; ++i) {
len[i] = one[i].second - one[i].first;
}
RMQ rmq(len);
Vec<ll> ret(Q);
for (int i = 0; i < Q; ++i) {
R[i] += 1;
const auto lb = std::lower_bound(one.begin(), one.end(), std::pair<int, int>(L[i], 0)) - one.begin();
const auto ub = std::lower_bound(one.begin(), one.end(), std::pair<int, int>(R[i], 0)) - one.begin();
int max = 0;
if (lb > 0 and one[lb - 1].second > L[i]) {
setmax(max, one[lb - 1].second - L[i]);
}
if (lb < ub) {
setmax(max, std::min(one[ub - 1].second, R[i]) - one[ub - 1].first);
setmax(max, rmq.fold(lb, ub - 1));
}
ret[i] = (R[i] - L[i]) * 2 - max;
}
return ret;
}
}
