#include <bits/stdc++.h>
using namespace std;
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 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 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;
for(int u=val;u<=MAXV;u++)
aux -= (prefcnt[u][poz[val-1]] - prefcnt[u][le-1]) * u;
aux += aint_val[val][poz[val-1]];
int mypoz = find(ri, aux, val);
poz[val] = max(poz[val-1], mypoz);
rez += prefcnt[val][ri] - prefcnt[val][poz[val]];
}
cout<<rez<<"\n";
}
return 0;
}
