#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
int v[400001];
struct numbers
{
int nr;
int id;
} ps[400001];
int jump[400005][4];
int f[400001];
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int n,i,nr = 2e9,j,l,r,cnt = -1;
int cur = -1;
cin>>n;
for(i = 0; i < n; i++)
{
cin>>v[i];
ps[i + 1] = {ps[i].nr + v[i],i + 1};
}
sort(ps,ps + n + 1,[&](numbers a,numbers b)
{
return a.nr < b.nr;
});
for(i = 0; i <= n; i++)
{
if(cur != ps[i].nr)
{
cur = ps[i].nr;
cnt++;
}
ps[i].nr = cnt;
}
sort(ps,ps + n + 1,[&](numbers a,numbers b)
{
return a.id < b.id;
});
f[ps[n].nr] = n;
for(i = n - 1; i >= 0; i--)
{
if(f[ps[i].nr] != 0 && nr > f[ps[i].nr])
{
nr = f[ps[i].nr];
}
jump[i][0] = (nr==2e9?n + 1:nr);
f[ps[i].nr] = i;
}
jump[n + 1][0] = n + 1;
jump[n][0] = n + 1;
for(i = 1; i <= 3; i++)
{
for(j = 0; j <= n + 1; j++)
{
///octo jump
jump[j][i] = jump[jump[jump[jump[jump[jump[jump[jump[jump[jump[jump[jump[jump[jump[jump[jump[j][i - 1]][i - 1]][i - 1]][i - 1]][i - 1]][i - 1]][i - 1]][i - 1]][i - 1]][i - 1]][i - 1]][i - 1]][i - 1]][i - 1]][i - 1]][i - 1];
}
}
int q,ans = 0,p;
cin>>q;
for(i = 0; i < q; i++)
{
cin>>l>>r;
l--;
r--;
cur = l,ans = 0;
for(j = 3; j >= 0; j--)
{
for(p = 0; p < 16; p++)
{
if(cur != n && jump[cur][j] <= r + 1)
{
cur = jump[cur][j];
ans+=(1<<(j*4));
}
}
}
cout<<ans<<'\n';
}
return 0;
}
