#pragma GCC optimize("O3,unroll-loops")
#include <iostream>
#include <vector>
using namespace std;
const int INF = 1e9;
int n, MAXV;
int a[200005];
int aint[102][530000], aint_val[102][200005];
int prefcnt[102][200005];
int v[200005];
void build(int nod, int st, int dr, int c)
{
if(st == dr)
{
aint[c][nod] = INF;
return;
}
int mij = (st + dr) / 2;
build(nod*2, st, mij, c);
build(nod*2+1, mij+1, dr, c);
aint[c][nod] = min(aint[c][nod*2], aint[c][nod*2+1]);
}
void build_aint(int lim)
{
for(int i=1;i<=n;i++)
{
if(a[i] <= lim)
v[i] = v[i-1] - a[i];
else
v[i] = v[i-1] + a[i];
aint_val[lim][i] = v[i];
}
build(1,1,n,lim);
}
void upd(int nod, int st, int dr, int poz, int newv, int c)
{
if(st == dr)
{
aint[c][nod] = newv;
return;
}
int mij = (st + dr) / 2;
if(poz <= mij) upd(nod*2,st,mij,poz,newv,c);
else upd(nod*2+1,mij+1,dr,poz,newv,c);
aint[c][nod] = min(aint[c][nod*2], aint[c][nod*2+1]);
}
int aint_search(int nod, int st, int dr, int le, int aux, int val, int minri)
{
if(st == dr)
{
if(st < n && st >= le && minri - aint_val[val][st] + aint_val[val - 1][st] - aint_val[val - 1][le] + aux >= 0)
return st;
return -1;
}
int mij = (st + dr) / 2;
if(mij >= le && min(minri, aint[val][nod*2+1]) - aint_val[val][mij] + aint_val[val - 1][mij] - aint_val[val - 1][le] + aux >= 0)
{
int x = aint_search(nod*2,st,mij,le,aux,val,min(minri, aint[val][nod*2+1]));
if(x != -1)
return x;
return mij;
}
return aint_search(nod*2+1,mij+1,dr,le,aux,val,minri);
}
int solve(int le, int ri, int val, int aux)
{
int x = aint_search(1,1,n,le,aux,val,INF);
if(x == -1 || x > ri)
x = ri;
return x;
}
int qle[200005], qri[200005], sol[200005];
vector<int> ofri[200005];
int poz[105];
int solve_qry(int le, int ri)
{
poz[0] = le - 1;//the last position with "+"
int rez = 0;
int aux = 0;
for(int val=1;val<=MAXV;val++)
{
poz[val] = solve(poz[val-1], ri, val, aux);
rez += prefcnt[val][ri] - prefcnt[val][poz[val]];
aux += aint_val[val - 1][poz[val]] - aint_val[val - 1][poz[val - 1]];
}
return rez;
}
signed main()
{
ios_base::sync_with_stdio(0);cin.tie(0);
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
MAXV = max(MAXV, a[i]);
}
for(int lim=0;lim<=MAXV;lim++)
build_aint(lim);
for(int val=1;val<=MAXV;val++)
for(int i=1;i<=n;i++)
prefcnt[val][i] = prefcnt[val][i-1] + (a[i] == val);
int q;
cin>>q;
for(int i=1;i<=q;i++)
{
cin>>qle[i]>>qri[i];
ofri[qri[i]].push_back(i);
}
for(int ri=1;ri<=n;ri++)
{
for(int lim=0;lim<=MAXV;lim++)
upd(1,1,n,ri,aint_val[lim][ri],lim);
for(int qid:ofri[ri])
{
sol[qid] = solve_qry(qle[qid], qri[qid]);
}
}
for(int i=1;i<=q;i++)
cout<<sol[i]<<"\n";
return 0;
}
