#include <bits/stdc++.h>
using namespace std;
struct segTree{
int *st;
void build(int l, int r, int ind, int arr[]){
if(l==r){
st[ind]=arr[l];
return;
}
int mid = (l+r)/2;
build(l,mid,ind*2+1,arr);
build(mid+1,r,ind*2+2,arr);
st[ind]=min(st[ind*2+1],st[ind*2+2]);
}
segTree(){
}
segTree(int n, int arr[]){
int x = ceil(log2(n));
x++;
st=new int[(1<<x)];
build(0,n-1,0,arr);
}
int query(int l, int r, int s, int e, int ind){
if(e<l||s>r){
return 1e9;
}
if(s<=l&&r<=e){
return st[ind];
}
int mid = (l+r)/2;
return min(query(l,mid,s,e,ind*2+1),query(mid+1,r,s,e,ind*2+2));
}
};
const int mxa = 106;
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
int a[n];
for(int &i : a){
cin >> i;
}
///precompute EVERYTHING
int cnt[mxa][n];
for(int i = 0;i<mxa;i++){
fill(cnt[i],cnt[i]+n,0);
}
int pref[mxa][n];
vector<segTree> segs(mxa);
for(int j = 0;j<mxa;j++){
pref[j][0]= (a[0]<=j) ? -a[0] : a[0];
cnt[j][0]=(a[0]==j);
for(int i = 1;i<n;i++){
pref[j][i]=pref[j][i-1]+(a[i]<=j ? -a[i] : a[i]);
cnt[j][i]=cnt[j][i-1]+(a[i]==j);
}
segs[j]=segTree(n,pref[j]);
}
int q;
cin >> q;
while(q--){
int l,r;
cin >> l >> r;
l--;r--;
int ol = l;
int ans = 0;
int sum = 0;
for(int i = 1;i<mxa;i++){
///find greatest index for p
int lo = l;
int hi = r;
while(lo<hi){
///all ind > mid have i as -ve.
int mid = (lo+hi)/2;
///check
int lefsum = pref[i-1][mid] - (ol ? pref[i-1][ol-1] : 0);
lefsum+=sum;
if(segs[i].query(0,n-1,mid+1,r,0)-segs[i].query(0,n-1,mid,mid,0)+lefsum>=0){
hi=mid;
}
else{
lo=mid+1;
}
}
l=lo;
///cnt i till l use to add to sum.
sum+=2*i*(cnt[i][l]-(ol ? cnt[i][ol-1] : 0));
///find i from l to r use to add to ans.
ans+=cnt[i][r]-cnt[i][l];
}
cout << ans << "\n";
}
return 0;
}
