#include <bits/stdc++.h>
using namespace std;
#define int long long
const int INF = 1e18;
const int MAXV = 100;//--------------------------------------------------------
int n;
int a[200005];
int aint[105][530000], aint_val[105][200005];
int prefcnt[105][200005];
int v[200005];
void build(int nod, int st, int dr, int c)
{
if(st == dr)
{
aint[c][nod] = v[st];
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);
}
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_find(int nod, int st, int dr, int ri, int k, int c)//the rightmost position x such that aint_val[x] < k && x <= ri
{
if(st > ri)
return -1;
if(st == dr)
{
if(aint[c][nod] >= k && st <= ri)
return -1;
return st;
}
int mij = (st + dr) / 2;
if(aint[c][nod*2 + 1] < k)
{
int x = aint_find(nod*2+1, mij+1, dr, ri, k, c);
if(x != -1)
return x;
}
return aint_find(nod*2, st, mij, ri, k, c);
}
int find(int ri, int k, int c)
{
for(int i=ri;i>=1;i--)
if(aint_val[c][i] < k)
return i;
return -1;
//return aint_find(1,1,n,ri,k,c);
}
int solve(int le, int ri, int val, int aux)
{
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,ri,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 poz[105];
signed main()
{
ios_base::sync_with_stdio(0);cin.tie(0);
cin>>n;
for(int i=1;i<=n;i++)
cin>>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++)
{
int le, ri;
cin>>le>>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]] - prefcnt[u][le - 1]) * u;
aux -= (prefcnt[u][poz[val-1]] - prefcnt[u][poz[u]]) * 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);
rez += prefcnt[val][ri] - prefcnt[val][poz[val]];
}
cout<<rez<<"\n";
}
return 0;
}
