#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 TAM 100000
#define all(a) a.begin (), a.end ()
typedef long long int ll;
ll m[5010][5010];
ll tree[4*TAM+40][4];
ll v[TAM+10];
int y;
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, a, (a+b)/2);
init(2*node+1, (a+b)/2+1, b);
tree[node][1]=max(tree[2*node][1],max(tree[2*node+1][1], tree[2*node][2]+tree[2*node+1][0]));
if(b-(a+b)/2==tree[2*node+1][2])tree[node][2]=tree[node*2][2] + (b-(a+b)/2);
else tree[node][2] = tree[node*2+1][2];
if((a+b)/2+1-a==tree[2*node][0])tree[node][0]=tree[node][0] = ((a+b)/2-a+1) + tree[node*2+1][0];
else tree[node][0] = tree[node*2][0];
}
int query(int node, int a, int b, int p, int q, int pos){
if(q<a or b<p)return 0;
if(p<=a and b<=q)return tree[node][pos];
if(pos==1){
int ans1=query(2*node, a, (a+b)/2, p , q, 1);
int ans2=query(2*node+1,(a+b)/2+1, b, p, q, 1);
int ans3=query(2*node, a, (a+b)/2, p, q, 2)+query(2*node+1, (a+b)/2+1, b, p, q, 0);
return max(ans1, max(ans2, ans3));
}else{
if(pos==2){
int ans2=MIN;
int ans1=query(2*node,(a+b)/2+1, b, p, q, 0);
if(ans1==((a+b)/2-max(a, p)+1))ans2=ans1+query(2*node+1, a, (a+b)/2, p, q, 0);
return max(ans1, ans2);
}else{
int ans2=MIN;
int ans1=query(2*node+1, a, (a+b)/2, p, q, 2);
if(ans1==(min(b, q)-(a+b)/2))ans2=ans1+query(2*node, (a+b)/2+1,b, p, q, 2);
return max(ans1, ans2);
}
}
}
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();
y=n;
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(1, 0, n-1);
for (int k = 0; k < Q; ++k) {
ll s1=0;
ll s=query(1, 0, n-1, l[k] , r[k], 1);
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(int i=1;i<4*4;i++)cout<<tree[i][0]<<" "<<tree[i][1]<<" "<<tree[i][2]<<endl;
for (size_t j = 0; j < C.size(); ++j) {
printf("%lld\n", v1[j]);
printf("%lld\n", C[j]);
}
return 0;
}
*/
