#ifndef LOCAL
#include "meetings.h"
#endif
#include <bits/stdc++.h>
#define FOR(i,p,k) for(int i=(p);i<=(k);++i)
#define REP(i,n) FOR(i,0,(n)-1)
#define inf 1000000000000000000ll
using namespace std;
typedef long long ll;
vector<ll> minimum_costs(vector<int> h, vector<int> l, vector<int> p){
int n = h.size();
int q = l.size();
if(n <= 5000 && q <= 5000){
vector maks(n, vector(n, 0));
REP(i, n){
maks[i][i] = h[i];
FOR(j, i+1, n-1) maks[i][j] = max(maks[i][j-1], h[j]);
}
vector doprawej(n, vector(n, 0ll));
vector dolewej(n, vector(n, 0ll));
REP(i, n){
doprawej[i][i] = dolewej[i][i] = h[i];
FOR(j, i+1, n-1) dolewej[i][j] = dolewej[i][j-1]+maks[i][j];
for(int j = i; ~--j;) doprawej[j][i] = doprawej[j+1][i]+maks[j][i];
}
vector<ll> ret(q);
REP(nr, q){
int a = l[nr], b = p[nr];
ret[nr] = inf;
FOR(i, a, b) ret[nr] = min(ret[nr], doprawej[a][i]+dolewej[i][b]-h[i]);
}
return ret;
}
vector<int> lewo(n, 0), prawo(n, 0);
REP(i, n) if(h[i] == 1) lewo[i] = 1 + (i ? lewo[i-1] : 0);
for(int i = n; ~--i;) if(h[i] == 1) prawo[i] = 1 + (i+1<n ? prawo[i+1] : 0);
struct przedzialowiec{
int N;
vector<int> drz;
przedzialowiec(int n){
for(N = 1; N < n;) N <<= 1;
drz.resize(N<<1, 0);
}
void ustaw(int poz, int wart){
for(poz += N, drz[poz] = wart; poz >>= 1;) drz[poz] = max(drz[poz<<1], drz[poz<<1|1]);
}
int maks(int p, int k){
int ret = 0;
for(p+=N, k+=N+1; p<k; p>>=1, k>>=1){
if(p&1) ret = max(ret, drz[p++]);
if(k&1) ret = max(ret, drz[--k]);
}
return ret;
}
} prz(n);
REP(i, n) prz.ustaw(i, prawo[i]);
vector<ll> ret(q);
REP(nr, q){
int a = l[nr], b = p[nr];
int t = lewo[b];
ret[nr] = max(t, prz.maks(a, b-t));
}
return ret;
}
#ifdef LOCAL
int main(){
int n, q;
scanf("%d%d", &n, &q);
vector<int> h(n);
REP(i, n) scanf("%d", &h[i]);
vector<int> l(q), p(q);
REP(i, q) scanf("%d%d", &l[i], &p[i]);
vector<ll> ret = minimum_costs(h, l, p);
for(ll x : ret) printf("%lld\n", x);
return 0;
}
#endif
