#include <bits/stdc++.h>
using namespace std;
#define rep(i, l, r) for(int i = (l); i < (r); ++i)
#define sz(v) (int)v.size()
#define dbg(x) "[" #x " = " << (x) << "]"
#define all(v) begin(v), end(v)
#define compact(v) v.erase(unique(all(v)), end(v))
#define file(name) if(fopen(name".inp", "r")){ freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
template<typename T>
bool minimize(T& a, const T& b){
if(a > b){
return a = b, true;
}
return false;
}
template<typename T>
bool maximize(T& a, const T& b){
if(a < b){
return a = b, true;
}
return false;
}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
using ll = long long;
using ld = long double;
using ull = unsigned long long;
using vi = vector<int>;
using vl = vector<ll>;
const int MAX = 4e5 + 2;
const int L = 5;
int N, a[MAX], pw16[L], lift[L][MAX], p[MAX];
long long pref[MAX];
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
//file("task");
cin >> N;
long long sum = 0;
for(int i = 1; i <= N; ++i){
cin >> a[i];
pref[i] = pref[i - 1] + a[i];
p[i] = i;
}
memset(lift, 0x3f, sizeof(lift));
int inf = lift[0][0];
sort(p, p + N + 1, [&](int i, int j){ return (pref[i] < pref[j]) || (pref[i] == pref[j] && i < j); });
for(int i = 0; i <= N; ++i){
while(i < N && pref[p[i]] == pref[p[i + 1]]){
if(p[i] < N) lift[0][p[i] + 1] = p[i + 1] + 1;
++i;
}
if(p[i] < N) lift[0][p[i] + 1] = inf;
}
pw16[0] = 1;
pw16[1] = 16;
for(int i = 2; i < L; ++i){
pw16[i] = pw16[i - 1] * 16;
}
for(int i = N - 1; i >= 1; --i){
minimize(lift[0][i], lift[0][i + 1]);
}
for(int i = 1; i < L; ++i){
for(int j = 1; j <= N; ++j){
lift[i][j] = j;
for(int rep = 0; rep < 16; ++rep){
if(lift[i][j] == inf) break;
lift[i][j] = lift[i - 1][lift[i][j]];
}
}
}
int Q, l, r, ans = 0;
cin >> Q;
while(Q--){
cin >> l >> r;
++r; ans = 0;
for(int i = L - 1; i >= 0; --i){
while(lift[i][l] <= r){
ans += pw16[i];
l = lift[i][l];
}
}
cout << ans << '\n';
}
return 0;
}
