#include <bits/stdc++.h>
#define MAX 405000
#define LOG 19
using ll = long long;
int N;
int jump[MAX][2];
int pulo_origem[MAX];
void simular_camada(int u){
for(int i=0;i!=N;++i)jump[i][0]=pulo_origem[i];
for(int j=1;j!=u+1;++j){
int cord = j&1;
int oposto = !cord;
for(int i=0;i!=N;++i){
int x = jump[i][oposto];
if(x<0)jump[i][cord]=x-1;
else jump[i][cord]=jump[x][oposto];
}
}
}
int array[MAX];
ll comprime[MAX];
int sz;
void work(){
ll s=0;
for(int i=0;i!=N;++i){
s+=array[i];
comprime[i+1]=s;
}
// std::sort(comprime,&comprime[N+5]);
sz=N+5;
}
int find(ll x){
int l=0,r=sz-1;
while(l<r){
int m = (l+r)/2;
if(comprime[m]>=x){
r=m;
}else l=m+1;
}
return l;
}
int respostas_comp[MAX];
void computa(void){
for(auto&x:respostas_comp)x=-7;
for(int i=0;i!=N;++i)std::cin>>array[i];
work();
int prev=-7;
respostas_comp[find(0)]=-1;
ll s=0;
for(int i=0;i!=N;++i){
ll x=array[i];
s+=x;
ll hsh=find(s);
if(respostas_comp[hsh]!=-7){
prev=std::max(prev,respostas_comp[hsh]);
}
pulo_origem[i]=prev;
std::cout<<pulo_origem[i]<<" ";
respostas_comp[hsh]=i;
}
std::cout<<"\n";
}
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
std::cin>>N;
computa();
int Q;
std::cin>>Q;
int ans[Q]={},pos[Q],lim[Q];
for(int i=0;i!=Q;++i){
int l,r;
std::cin>>l>>r;l-=2;--r;
pos[i] = r;
lim[i] = l;
}
///Exponenciacao binaria
for(int j=LOG-1;j!=-1;--j){
simular_camada(j);
for(int i=0;i!=Q;++i){
if(pos[i]>=0&&jump[pos[i]][j&1]>=lim[i]){
ans[i]+=1<<j;
pos[i]=jump[pos[i]][j&1];
}
}
}
for(int i=0;i!=Q;++i)std::cout<<ans[i]<<"\n";
}
