#include<bits/stdc++.h>
#define taskname "B"
using namespace std;
typedef long long ll;
const int lim = 4e5 + 5;
const int INF = 1e9 + 36;
template<class T>void maximize(T& a, T b){
if(a < b){
a = b;
}
}
const int pw100[3] = {1, 100, 10000};
int n, q, up[3][lim];
ll f[lim];
namespace sub1{
void solve(){
for(int _ = 0; _ < q; _++){
int l, r;
cin >> l >> r;
r++;
vector<ll>dp(n + 2, -INF);
dp[l] = 0;
for(int i = l + 1; i <= r; i++){
dp[i] = max(dp[i - 1], dp[up[0][i]] + 1);
}
cout << dp[r] << "\n";
}
}
}
namespace sub23{
int bit[lim];
void update(int p, int x){
for(; p < n + 2; p += p & -p){
maximize(bit[p], x);
}
}
int get(int l, int r){
int ans = 0;
for(; r >= l; ){
int nr = r - (r & -r);
if(nr < l - 1){
maximize(ans, up[0][r--]);
}
else{
maximize(ans, bit[r]);
r = nr;
}
}
return ans;
}
void solve(){
for(int i = 1; i < n + 2; i++){
update(i, up[0][i]);
}
for(int i = 2; i < n + 2; i++){
up[0][i] = get(max(1, up[0][i]), i);
}
for(int i = 1; i < 3; i++){
for(int j = 0; j < n + 2; j++){
int t = j;
for(int z = 0; z < 100; z++){
t = up[i - 1][t];
}
up[i][j] = t;
}
}
for(int _ = 0; _ < q; _++){
int l, r, ans = 0;
cin >> l >> r;
for(int i = 2, x = r + 1; i > -1; i--){
for(int z = 0; z < 100; z++){
int nx = up[i][x];
if(nx >= l){
x = nx;
ans += pw100[i];
}
else{
break;
}
}
}
cout << ans << "\n";
}
}
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
if(fopen(taskname".inp", "r")){
freopen(taskname".inp", "r", stdin);
}
memset(up, f[0] = f[1] = 0, sizeof(up));
cin >> n;
for(int i = 2, x; i < n + 2; i++){
cin >> f[i];
f[i] += f[i - 1];
}
vector<int>p(n + 2);
iota(p.begin(), p.end(), 0);
sort(p.begin(), p.end(), [&] (int i, int j){
return make_pair(f[i], i) < make_pair(f[j], j);
});
for(int i = 1; i < n + 2; i++){
if(f[p[i]] == f[p[i - 1]]){
up[0][p[i]] = p[i - 1];
}
}
cin >> q;
if(max(n, q) <= 5000){
sub1::solve();
}
else{
sub23::solve();
}
}
