#include <bits/stdc++.h>
using namespace std;
const int lg = 18;
const int mxn = 2e5+5;
struct sparseTable{
int spar[mxn][lg];
sparseTable(){
}
void build(int n, int arr[]){
for(int i = 0;i<n;i++){
fill(spar[i],spar[i]+lg,1e9);
spar[i][0]=arr[i];
}
for(int i = n-1;i>=0;i--){
for(int j = 1;j<lg;j++){
spar[i][j]=spar[i][j-1];
int ind = i+(1<<(j-1));
if(ind<n){
spar[i][j]=min(spar[i][j],spar[ind][j-1]);
}
}
}
}
int query(int l, int r){
if(l>r)
return 1e9;
int dif = (r-l+1);
dif = (31-__builtin_clz(dif));
return min(spar[l][dif],spar[r-(1<<dif)+1][dif]);
}
};
int mxa = 101;
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
int a[n];
for(int &i : a){
cin >> i;
}
mxa = *max_element(a,a+n)+1;
///precompute EVERYTHING
///precompute NOTHING
int q;
cin >> q;
array<int,2>quers[q];
int ol[q];
for(int i = 0;i<q;i++){
cin >> quers[i][0];
cin >> quers[i][1];
quers[i][0]--;
ol[i]=quers[i][0];
quers[i][1]--;
}
int cnt[n];
fill(cnt,cnt+n,0);
int pref[n];
int laspref[n];
fill(laspref,laspref+n,0);
sparseTable st;
int ans[q];
int sum[q];
fill(sum,sum+q,0);
fill(ans,ans+q,0);
for(int i = 0;i<mxa;i++){
pref[0]=(a[0]<=i) ? -a[0] : a[0];
cnt[0]=(a[0]==i);
for(int j = 1;j<n;j++){
pref[j]=pref[j-1]+(a[j]<=i ? -a[j] : a[j]);
cnt[j]=cnt[j-1]+(a[j]==i);
}
st.build(n,pref);
for(int j = 0;j<q;j++){
int l = quers[j][0];
int r = quers[j][1];
///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 = laspref[mid] - (ol[j] ? laspref[ol[j]-1] : 0);
lefsum+=sum[j];
if(st.query(mid+1,r)-st.query(mid,mid)+lefsum>=0){
hi=mid;
}
else{
lo=mid+1;
}
}
quers[j][0]=lo;
///cnt i till l use to add to sum.
sum[j]+=2*i*(cnt[lo]-(ol[j] ? cnt[ol[j]-1] : 0));
///find i from l to r use to add to ans.
ans[j]+=cnt[r]-cnt[lo];
}
for(int i = 0;i<n;i++){
laspref[i]=pref[i];
}
}
for(int i : ans){
cout << i << "\n";
}
return 0;
}
