#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
#define MIN -1
#define MAX 1000000000000000000
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define all(a) a.begin (), a.end ()
typedef long long int ll;
ll m[5010][5010];
ll tree[400100][4];
ll v[100100];
vector <ll> v1;
void init(int node, int a, int b){
if(a==b){
if(v[a]==2){
tree[node][0]=0;
tree[node][1]=0;
tree[node][2]=0;
}else {
tree[node][0]=1;
tree[node][1]=1;
tree[node][2]=1;
}
return ;
}
init(2*node+1, a, (a+b)/2);
init(2*node+2, (a+b)/2+1, b);
if(tree[2*node+1][0]>=1){
tree[node][0]=tree[2*node+1][0]+tree[2*node+2][0];
}else tree[node][0]=0;
if(tree[2*node+2][2]>=1){
tree[node][2]=tree[2*node+1][2]+tree[2*node+2][2];
}else{
tree[node][2]=0;
}
if(tree[2*node+1][2]>=1 and tree[2*node+2][0]>=1){
tree[node][1]=tree[2*node+1][1]+tree[2*node+2][1];
}else tree[node][1]=max(tree[2*node+1][1], tree[2*node+2][1]);
}
int query(int node, int a, int b, int p, int q){
if(q<a or b<p)return 0;
if(p<=a and b<=q)return tree[node][1];
if(tree[2*node+1][2]>=1 and tree[2*node+2][0]>=1){
return query(2*node+1,a, (a+b)/2, p , q)+query(2*node+2,(a+b)/2+1,b,p, q);
}else return max (query(2*node+1,a, (a+b)/2, p , q),query(2*node+2,(a+b)/2+1,b,p, q));
}
vector<ll> minimum_costs(vector<int> h, vector<int > l,vector<int > r) {
int n=h.size ();
//memset(m, 0, sizeof h.size ());
int Q = l.size();
vector<ll> C(Q);
int sw=0;
for(int i=0;i<n;i++){
if(h[i]>2){
sw=1;
break;
}
}
if(sw==1){
memset(m, 0, sizeof h.size());
for(int i=0;i<n;i++){
int maxi=h[i];
for(int j=i-1;j>=0;j--){
m[i][j]+=max(maxi, h[j]);
m[i][j]+=m[i][j+1];
maxi=max(maxi, h[j]);
}
maxi=h[i];
m[i][i]=h[i];
for(int j=i+1;j<n;j++){
m[i][j]+=max(h[j], maxi);
m[i][j]+=m[i][j-1];
maxi=max(h[j], maxi);
}
}
for (int k = 0; k < Q; ++k) {
ll mini=MAX;
for(int i=l[k];i<=r[k];i++){
if(i==l[k]){
mini=min(m[i][r[k]], mini);
}else{
mini=min(m[i][r[k]]+m[i][l[k]], mini);
}
}
C[k]=mini;
}
return C;
}
for(int i=0;i<n;i++){
v[i]=h[i];
}
init(0, 0, n);
for (int k = 0; k < Q; ++k) {
ll s1=0;
ll s=query(0, 0, n, l[k] , r[k]);
v1.push_back(s);
int t=r[k]+1-l[k];
s1+=(t-s)*2;
s1+=s;
C[k]=s1;
}
return C;
}
/*namespace {
int read_int() {
int x;
if (scanf("%d", &x) != 1) {
fprintf(stderr, "Error while reading input\n");
exit(1);
}
return x;
}
} // namespace
int main() {
int N = read_int();
int Q = read_int();
std::vector<int> H(N);
for (int i = 0; i < N; ++i) {
H[i] = read_int();
}
std::vector<int> L(Q), R(Q);
for (int j = 0; j < Q; ++j) {
L[j] = read_int();
R[j] = read_int();
}
std::vector<long long> C = minimum_costs(H, L, R);
for (size_t j = 0; j < C.size(); ++j) {
// printf("%lld\n", v1[j]);
printf("%lld\n", C[j]);
}
return 0;
}
*/
