#include "meetings.h"
#include <bits/stdc++.h>
#define MAX 1e9+7
#define SMAX 1e18+7
#define all(a) a.begin (), a.end ()
#define F first
#define S second
#define MIN -1
#define pb push_back
#define mk make_pair
#define mem(a, c) memset(a, c, sizeof a)
#define pp pop_back
using namespace std;
typedef long long int ll;
typedef vector <int> vi;
typedef pair<ll, ll> ii;
typedef vector<ii> vii;
typedef vector <ll> vll;
ll mt[5010][5010];
int n, q;
const int N=1e5+10;
vector<pair<ii, ii> > tree;
pair<ii, ii> op(pair<ii, ii> a, pair<ii, ii> b){
pair<ii, ii > ans;
ans.F.S=a.F.S+b.F.S;
ans.F.F=max(a.F.F, max(b.F.F, a.S.S+b.S.F));
if(b.S.S==b.F.S)ans.S.S=a.S.S+b.S.S;
else ans.S.S=b.S.S;
if(a.S.F==a.F.S)ans.S.F=a.S.F+b.S.F;
else ans.S.F=a.S.F;
return ans;
}
void upd(int node, int in ,int fin, int pos, int val){
if(pos>fin || pos<in)return;
if(in==fin){
tree[node].F.S=1;
tree[node].F.F=val;
tree[node].S.F=val;
tree[node].S.S=val;
return;
}
int mid=(in+fin)/2;
upd(2*node+1, in, mid, pos, val);
upd(2*node+2, mid+1, fin, pos, val);
tree[node]=op(tree[2*node+1], tree[2*node+2]);
}
pair<ii, ii> vacio;
pair<ii, ii> query(int node, int in, int fin, int l, int r){
if(in>r || fin<l)return vacio;
if(in>=l && fin<=r )return tree[node];
int mid=(in+fin)/2;
return op(query(2*node+1, in, mid, l, r), query(2*node+2, mid+1, fin, l, r));
}
vector<long long> minimum_costs(vector<int> H,vector<int> l,vector<int> r) {
vacio=mk(mk(0, 0), mk(0, 0));
vll v;
vll total;
n=H.size ();
q=l.size ();
tree=vector<pair<ii, ii> > (N*4);
for(int i=0;i<n;i++)v.pb(H[i]);
int sw=0;
for(int i=0;i<n;i++){
if(v[i]>2)sw=1;
}
if(!sw){
for(int i=0;i<n;i++){
if(v[i]==2)upd(0, 0, n-1, i, 0);
else upd(0, 0, n-1, i, 1);
}
// for(int i=0;i<=30;i++)cout<<tree[i].F.F<<" ";
// cout<<endl;
for(int i=0;i<q;i++){
pair<ii, ii> ans=query(0, 0,n-1, l[i], r[i]);
ll ans1=(r[i]-l[i]+1)*2;
ans1-=ans.F.F;
total.pb(ans1);
}
return total;
}
mem(mt, 0);
//if(sw){
for(int i=0;i<n;i++){
ll maxi=v[i];
mt[i][i]=v[i];
for(int j=i-1;j>=0;j--){
maxi=max(maxi, v[j]);
mt[i][j]+=maxi+mt[i][j+1];
}
maxi=max(v[i], v[i+1]);
mt[i][i+1]=maxi;
for(int j=i+2;j<n;j++){
maxi=max(maxi, v[j]);
mt[i][j]+=maxi+mt[i][j-1];
}
}
/*for(int i=0;i<n;i++){
for(int j=0;j<n;j++)cout<<mt[i][j]<<" ";
cout<<endl;
}*/
for(int i=0;i<q;i++){
ll ans=SMAX;
for(int j=0;j<n;j++){
if(r[i]==j)ans=min(ans, mt[j][l[i]]);
else
ans=min(ans, mt[j][l[i]]+mt[j][r[i]]);
}
total.pb(ans);
}
return total;
// }
}
/*
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", C[j]);
}
return 0;
}
*/
