#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];
unordered_map<long long, int> last;
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];
sum += a[i];
}
pw16[0] = 1;
pw16[1] = 16;
for(int i = 2; i < L; ++i){
pw16[i] = pw16[i - 1] * 16;
}
memset(lift, 0x3f, sizeof(lift));
int inf = lift[0][0];
for(int i = N; i >= 0; --i){
//select smallest j such sum [i...j) = 0
if(i < N) lift[0][i + 1] = (last.find(sum) == last.end() ? inf : last[sum] + 1);
if(i > 0) last[sum] = i;
sum -= a[i];
}
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;
}
