#include <bits/stdc++.h>
using namespace std;
const int lg = 20;
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);
ind=min(ind,n-1);
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));
for(int i = 0;i<lg;i++){
if(l+(1<<i)-1>r){
dif=i-1;
break;
}
}
int ans = 1e9;
for(int i = dif;i>=0;i--){
if(l+(1<<i)-1<=r){
ans=min(ans,spar[l][i]);
l+=(1<<i);
}
}
return ans;
return min(spar[l][dif],spar[r-(1<<dif)+1][dif]);
}
};
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;
}
mxa = *max_element(a,a+n)+2;
///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<sparseTable> 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].build(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(mid+1,r)-segs[i].query(mid,mid)+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;
}
