#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define ff first
#define ss second
#define INFL 1000000000000000099LL
#define pii pair<ll,ll>
#define vi vector<ll>
#define vii vector<pii>
const ll A=100;
ll n,a,b;
vi v;
vi v2[A+1];
vi pr={0};
vi pr2[A+1];
ll ns[200007],bn[200007];
vii zp[200007];
ll dz(ll a,ll b){
if(a>=0)return a/b;
return (a-b+1)/b;
}
ll mnn[200007];
ll mj[200007];
ll fnd(ll x){
return mj[x]==x?x:mj[x]=fnd(mj[x]);
}
void onion(ll a,ll b){
a=fnd(a);b=fnd(b);
mnn[b]=min(mnn[b],mnn[a]);
mj[a]=b;
}
int main(){
for(ll i=1;i<=A;i++)pr2[i].pb(0);
cin>>n;
for(ll i=0;i<n;i++){
cin>>a;
v.pb(a);v2[a].pb(i);
pr.pb(pr.back()+a);
for(ll j=1;j<=A;j++)pr2[j].pb(pr2[j].back());
pr2[a].back()-=2*a;
}
for(ll i=0;i<=n;i++)pr2[1][i]+=pr[i];
for(ll i=0;i<=n;i++)for(ll j=2;j<=A;j++)pr2[j][i]+=pr2[j-1][i];
ll q;cin>>q;
for(ll i=0;i<q;i++){
cin>>a>>b;
ns[i]=b-a+1;
zp[b].pb({a-1,i});
}
for(ll i=1;i<=A;i++){
for(ll j=0;j<=n;j++)mj[j]=j;
stack<pii>st;
st.push({-INFL,-1});
for(ll j=0;j<=n;j++){
mnn[j]=pr2[i][j];
while(mnn[j]<st.top().ff){
onion(st.top().ss,j);st.pop();
}
st.push({mnn[j],j});
for(pii k: zp[j]){
ll mn=mnn[fnd(k.ff)];
mn=mn+bn[k.ss]-pr2[i][k.ff];
ns[k.ss]+=dz(mn,i*2);
bn[k.ss]-=dz(mn,i*2)*i*2;
}
}
}
for(ll i=0;i<q;i++)cout<<ns[i]<<"\n";
}
