/**
* user: lendvaj-c30
* fname: Dorijan
* lname: Lendvaj
* task: SumZero
* score: 100.0
* date: 2020-12-04 07:54:53.165994
*/
#include <bits/stdc++.h>
#define x first
#define y second
#define pii pair<int,int>
using ll=long long;
#define pll pair<ll,ll>
#define vi vector<int>
#define vl vector<ll>
#define pb push_back
#define eb emplace_back
#define all(a) begin(a),end(a)
using namespace std;
const int N=400010,MOD=1e9+7,LOG=7,B=6;
const char en='\n';
const ll LLINF=1ll<<60;
void compress(vl&v)
{
vl v1=v;
sort(all(v1));
for (auto&a: v) a=lower_bound(all(v1),a)-v1.begin();
}
int n,q,cn[N],cncn[5000],ma,par[LOG+2][N],po[20];
void add(int a)
{
--cncn[cn[a]];
++cn[a];
if (cn[a]>3) while (1);
if (cn[a]==ma+1 && cncn[cn[a]]==0) ++ma;
++cncn[cn[a]];
}
void rem(int a)
{
--cncn[cn[a]];
if (cn[a]==ma && cncn[cn[a]]==0) --ma;
--cn[a];
++cncn[cn[a]];
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cin>>n;
vl v;
v.pb(0);
ll s=0;
for (int i=0;i<n;++i)
{
ll a;
cin>>a;
s+=a;
v.pb(s);
}
compress(v);
int r=-1;
for (int l=0;l<=n;++l)
{
while (r<n && ma<=1) add(v[++r]);
if (ma==2) par[0][l]=r;
else par[0][l]=n+1;
rem(v[l]);
//cout<<l<<' '<<r<<en;
}
po[0]=1;
for (int i=1;i<=LOG;++i) po[i]=po[i-1]*B;
par[0][n+1]=n+1;
for (int j=1;j<=LOG;++j) for (int i=0;i<=n+1;++i)
{
int u=i;
for (int k=0;k<B;++k) u=par[j-1][u];
par[j][i]=u;
}
cin>>q;
while (q--)
{
int l,r;
cin>>l>>r;
--l;
int an=0;
for (int j=LOG;j>=0;--j) while (par[j][l]<=r) an+=po[j],l=par[j][l];
cout<<an<<en;
}
}
