#include "meetings.h"
#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; i++)
#define FORD(i, b, a) for (int i = (b), _a = (a); i >= _a; i--)
#define REP(i, n) for (int i = 0, _n = (n); i < _n; i++)
#define FORE(i, v) for (__typeof((v).begin()) i = (v).begin(); i != (v).end(); i++)
#define ALL(v) (v).begin(), (v).end()
#define IS_INF(x) (std::isinf(x))
#define IS_NAN(x) (std::isnan(x))
#define fi first
#define se second
#define MASK(i) (1LL << (i))
#define BIT(x, i) (((x) >> (i)) & 1)
#define div ___div
#define prev ___prev
#define next ___next
#define left ___leftc
#define right ___right
#define __Im_sogood__ main()
#define TIME (1.0 * clock() / CLOCKS_PER_SEC)
#define __builtin_popcount __builtin_popcountll
using namespace std;
const int MAXSUBBEFORE5 = 1e5 + 5;
const int MAXN = 8e5 + 5;
const long long INF = 1e18;
const int INFINT = 1e9;
int n, q;
struct Node {
int L, pre, suf, ans; Node() { L = pre = suf = ans = -INFINT; }
Node(int x) {
L = 1; if(x == 1) pre = suf = ans = 1; else pre = suf = ans = 0;
}
};
Node operator+(const Node& left, const Node& right) {
if(left.ans == -INFINT) return right; if(right.ans == -INFINT) return left;
Node res; res.L = left.L + right.L; res.ans = max({left.ans, right.ans, left.suf + right.pre});
if(left.pre < left.L) res.pre = left.pre; else res.pre = left.L + right.pre;
if(right.suf < right.L) res.suf = right.suf; else res.suf = right.L + left.suf;
return res;
}
struct SegmentTree {
Node tree[MAXSUBBEFORE5 << 2];
void update(int idx, int l, int r, int pos, int val) {
if(r < pos || pos < l) return;
if(l == r) { tree[idx] = Node(val); return; }
int mid = (l + r) >> 1;
update(idx << 1, l, mid, pos, val);
update(idx << 1 | 1, mid + 1, r, pos, val);
tree[idx] = tree[idx << 1] + tree[idx << 1 | 1];
}
Node query(int idx, int l, int r, int u, int v) {
if(r < u || v < l) return Node();
if(u <= l && r <= v) return tree[idx];
int mid = (l + r) >> 1;
return query(idx << 1, l, mid, u, v) + query(idx << 1 | 1, mid + 1, r, u, v);
}
void Update(int pos, int val) { update(1, 0, n - 1, pos, val); }
int getSumLess(int l, int r) {
Node res = query(1, 0, n - 1, l, r);
return res.ans;
}
} st;
vector<long long> solve_subtask1(const vector<int>& H, const vector<int>& L, const vector<int>& R) {
vector<long long> answer; REP(i, q) {
int l = L[i], r = R[i]; long long ans = INF; FOR(j, l, r) {
long long res = H[j], mx = H[j]; FORD(k, j - 1, l) { mx = max(mx, (long long)H[k]);
res += mx; }
mx = H[j]; FOR(k, j + 1, r) { mx = max(mx, (long long)H[k]); res += mx; }
ans = min(ans, res);
}
answer.push_back(ans);
}
return answer;
}
// left[x]: sum i < x
// right[x]: sum i > x;
vector<long long> solve_subtask2Stack(const vector<int>& H, const vector<int>& L, const vector<int>& R) {
vector<long long> answer; vector<long long> left(n, 0), right(n, 0);
REP(i, q) {
int l = L[i], r = R[i]; long long ans = INF; stack<pair<long long, long long>> st;
st.push({H[l], 1ll}); long long sum = H[l]; FOR(j, l + 1, r) {
long long cur = 0;
while(st.size() && st.top().first <= H[j]) {
cur += st.top().second; sum -= st.top().second * st.top().first;
st.pop();
}
cur++;
sum += cur * H[j]; st.push({H[j], cur});
left[j] = sum - H[j];
}
while(st.size()) st.pop();
st.push({H[r], 1}); sum = H[r]; FORD(j, r - 1, l) {
long long cur = 0; while(st.size() && st.top().first <= H[j]) {
cur += st.top().second; sum -= st.top().second * st.top().first;
st.pop();
}
cur++; sum += cur * H[j]; st.push({H[j], cur});
right[j] = sum - H[j];
}
FOR(j, l, r) ans = min(ans, left[j] + right[j] + H[j]); answer.push_back(ans);
REP(i, n) left[i] = right[i] = 0;
}
return answer;
}
bool check_subtask3(const vector<int>& H) {
FORE(it, H) if((*it) > 2) return false; return (n <= 100000 && q <= 100000);
}
/*vector<long long> solve_subtask2DP(const vector<int>& H, const vector<int>& L, const vector<int>& R) {
}*/
vector<long long> solve_subtask3(const vector<int>& H, const vector<int>& L, const vector<int>& R) {
vector<long long> answer; REP(i, n) st.Update(i, H[i]); REP(i, q) {
int l = L[i], r = R[i]; answer.push_back(2 * (r - l + 1) - st.getSumLess(l, r));
}
return answer;
}
vector<long long> minimum_costs(vector<int> H, vector<int> L, vector<int> R) {
n = (int)H.size(); q = (int)L.size();
if(n <= 3000 && q<= 10) return solve_subtask1(H, L, R);
//else if(n <= 5000 && q <= 5000) return solve_subtask2DP(H, L, R);
else if(n <= 5000 && q <= 5000) return solve_subtask2Stack(H, L, R);
else if(check_subtask3(H)) return solve_subtask3(H, L, R);
return {};
}
/*void read_fake_input() {
int n, q; vector<int> H, L, R; cin >> n >> q; REP(i, n) {
int x; cin >> x; H.push_back(x);
} REP(i, q) { int x; cin >> x; L.push_back(x); } REP(i, q) {
int x; cin >> x; R.push_back(x);
}
vector<long long> res = minimum_costs(H, L, R); FORE(it, res) cout << (*it) << "\n";
}
__Im_sogood__{
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
read_fake_input();
cerr << "Time elapsed: " << TIME << " s.\n";
return 0;
}*/
