#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;
const int MAXV_INIT = 100;//--------------------------------------------------------
int MAXV;
int n;
int a[200005];
int aint[MAXV_INIT + 2][530000], aint_val[MAXV_INIT + 2][200005];
int prefcnt[MAXV_INIT + 2][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 qry(int nod, int st, int dr, int le, int ri, int c)
{
if(le > ri)
return INF;
if(le == st && dr == ri)
return aint[c][nod];
int mij = (st + dr) / 2;
return min(qry(nod*2,st,mij,le,min(mij,ri),c), qry(nod*2+1,mij+1,dr,max(mij+1,le),ri,c));
}
int aint_search(int nod, int st, int dr, int le, int aux, int val, int minri)
{
if(dr < le)
return -1;
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(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);
assert(x != -1);
assert(x <= ri);
return x;
int st = le, dr = ri, ans = -1;
while(st <= dr)
{
int mij = (st + dr) / 2;
bool bun = 1;
if(qry(1,1,n,mij+1,n,val) - aint_val[val][mij] + aint_val[val - 1][mij] - aint_val[val - 1][le] + aux >= 0)
{
bun = 1;
}
else
{
bun = 0;
}
if(bun)
{
ans = mij;
dr = mij - 1;
}
else
st = mij + 1;
}
assert(ans != -1);
return ans;
}
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;
for(int val=1;val<=MAXV;val++)
{
int aux = 0;
for(int u=1;u<val;u++)
{
aux += prefcnt[u][poz[u]] * u * 2 - prefcnt[u][le - 1] * u - prefcnt[u][poz[val-1]] * u;
}
for(int u=val;u<=MAXV;u++)
{
aux += (prefcnt[u][poz[val-1]] - prefcnt[u][le - 1]) * u;
}
assert(aux >= 0);
poz[val] = solve(poz[val-1], ri, val, aux);
assert(poz[val] >= poz[val-1]);
rez += prefcnt[val][ri] - prefcnt[val][poz[val]];
}
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;
}
