#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;
}
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++){
for(pii k: zp[j]){
ll mn=INFL;
for(ll m=j;m>=k.ff;m--){
mn=min(mn,pr2[i][m]);
}
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";
}
