// #pragma GCC target ("avx,avx2,fma")
// #pragma GCC optimize ("Ofast,inline") // O1 - O2 - O3 - Os - Ofast
// #pragma GCC optimize ("unroll-loops")
#include <bits/stdc++.h>
#include "meetings.h"
using namespace std;
#define rep(i, a, b) for (ll i = (a); i < (b); ++i)
#define per(i, a, b) for (ll i = (b) - 1; i >= (a); --i)
#define trav(a, x) for (auto &a : x)
#define all(x) x.begin(), x.end()
#define sz(x) (ll)x.size()
#define pb push_back
#define debug(x) cout<<#x<<" = "<<x<<endl
#define umap unordered_map
#define uset unordered_set
typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef pair<ll,pll> ppll;
typedef vector<ll> vll;
typedef vector<pll> vpll;
typedef vector<vll> vvll;
const ll INF = 1'000'000'007;
vll dist;
struct Node {
ll val,suf,pref,lo,hi;
Node *l,*r;
Node(ll L,ll R) : lo(L),hi(R) {
if(hi-lo==1) {
if(dist[lo]==1) val=suf=pref=1;
else val=suf=pref=0;
}
else {
ll mid=(lo+hi)/2;
l=new Node(lo,mid);
r=new Node(mid,hi);
auto item=comb({l->val,{l->pref,l->suf}},{r->val,{r->pref,r->suf}});
val=item.first;
pref=item.second.first;
suf=item.second.second;
}
}
ppll query(ll L,ll R) {
if(R<=lo||hi<=L) return {0,{0,0}};
if(L<=lo&&hi<=R) return {val,{pref,suf}};
auto a= comb(l->query(L,R),r->query(L,R));
//cout<<"lo = "<<lo<<" hi = "<<hi<<" val = "<<a.first<<" pref = "<<a.second.first<<" suf = "<<a.second.second<<endl;
return a;
}
ppll comb(ppll a,ppll b) {
ll curval,cursuf,curpref;
curval=max(a.first,b.first);
cursuf=b.second.second;
curpref=a.second.first;
if(a.first==l->hi-l->lo) curpref=a.first+b.second.first;
if(b.first==r->hi-r->lo) cursuf=b.first+a.second.second;
return {curval,{cursuf,curpref}};
}
};
ll n,q;
vll minimum_costs(vi H, vi L, vi R) {
n=sz(H);
q=sz(L);
vll answers(q);
ll pos=-1;
dist.assign(n,-1);
rep(i,0,n) dist[i]=H[i];
Node segtree(0,n);
rep(i,0,q) {
//cout<<"i = "<<i<<' '<<segtree.query(L[i],R[i]+1).first<<endl;
answers[i]=(R[i]-L[i]+1)*2-segtree.query(L[i],R[i]+1).first;
}
return answers;
}
/**
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;
}/**/
