#pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
// ----------- Fast Typing ------------
#define int long long
#define pb push_back
#define ff first
#define ss second
#define endl '\n'
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define vi vector<int>
#define ii pair<int, int>
#define vii vector<ii>
#define yes cout << "YES\n"
#define no cout << "NO\n"
// ----------- Ordered Set (policy-based) ------------
template <typename T>
using ordered_set = tree<
T,
null_type,
less<T>,
rb_tree_tag,
tree_order_statistics_node_update
>;
#ifndef ONLINE_JUDGE
// Forward declarations of print helpers
void _print(const string &s);
void _print(const char *s);
void _print(char c);
void _print(bool x);
void _print(long double x);
void _print(long x);
void _print(int x);
// Pair
template<typename T, typename V>
void _print(const pair<T, V> &p) {
cerr << "{"; _print(p.first); cerr << ", "; _print(p.second); cerr << "}";
}
// Tuple
template<class Tuple, size_t... I>
void _print_tuple(const Tuple &t, std::index_sequence<I...>) {
cerr << "(";
(( _print(get<I>(t)), cerr << (I + 1 == sizeof...(I) ? "" : ", ") ), ...);
cerr << ")";
}
template<typename... Ts>
void _print(const tuple<Ts...> &t) {
_print_tuple(t, std::index_sequence_for<Ts...>{});
}
// Vector
template<typename T>
void _print(const vector<T> &v) {
cerr << "[";
for (size_t i = 0; i < v.size(); ++i) {
_print(v[i]);
if (i + 1 < v.size()) cerr << ", ";
}
cerr << "]";
}
// Deque
template<typename T>
void _print(const deque<T> &v) {
cerr << "[";
for (size_t i = 0; i < v.size(); ++i) {
_print(v[i]);
if (i + 1 < v.size()) cerr << ", ";
}
cerr << "]";
}
// List
template<typename T>
void _print(const list<T> &l) {
cerr << "[";
bool first = true;
for (auto &x : l) {
if (!first) cerr << ", ";
_print(x);
first = false;
}
cerr << "]";
}
// Set
template<typename T>
void _print(const set<T> &s) {
cerr << "{";
bool first = true;
for (auto &x : s) {
if (!first) cerr << ", ";
_print(x);
first = false;
}
cerr << "}";
}
// Unordered set
template<typename T>
void _print(const unordered_set<T> &s) {
cerr << "{";
bool first = true;
for (auto &x : s) {
if (!first) cerr << ", ";
_print(x);
first = false;
}
cerr << "}";
}
// Map
template<typename T, typename V>
void _print(const map<T, V> &m) {
cerr << "{";
bool first = true;
for (auto &kv : m) {
if (!first) cerr << ", ";
_print(kv);
first = false;
}
cerr << "}";
}
// Unordered map
template<typename T, typename V>
void _print(const unordered_map<T, V> &m) {
cerr << "{";
bool first = true;
for (auto &kv : m) {
if (!first) cerr << ", ";
_print(kv);
first = false;
}
cerr << "}";
}
// C-style string
void _print(const char *s) { cerr << '"' << s << '"'; }
void _print(const string &s) { cerr << '"' << s << '"'; }
void _print(char c) { cerr << '\'' << c << '\''; }
void _print(bool x) { cerr << (x ? "true" : "false"); }
// Numbers
void _print(long double x) { cerr << (double)x; }
void _print(long x) { cerr << x; }
void _print(int x) { cerr << x; }
// Generic fallback for pointers / other printable types
template<typename T>
void _print(const T* p) {
if (p == nullptr) cerr << "nullptr";
else cerr << "ptr(" << (void*)p << ")";
}
// Variadic debug printer
void _debug() { cerr << '\n'; }
template<typename Head, typename... Tail>
void _debug(Head H, Tail... T) {
_print(H);
if constexpr (sizeof...(T) > 0) cerr << ", ";
_debug(T...);
}
#define debug(...) cerr << "[" << __FILE__ << ":" << __LINE__ << "] " << "[" << #__VA_ARGS__ << "] = ", _debug(__VA_ARGS__)
#else
#define debug(...) ((void)0)
#endif
// ----------- Random Generator ------------
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int randInt(int l, int r) {
return uniform_int_distribution<int>(l, r)(rng);
}
// ----------- Constants ------------
const int MOD = 1e9 + 7;
const int INF = 1e18;
const int N = 2e5 + 5;
// ----------- Useful Functions ------------
int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }
int lcm(int a, int b) { return (a / gcd(a, b)) * b; }
// ----------- Main Solve Function ------------
void solve() {
int n;
if (!(cin >> n)) return;
vi a(n+1), pr(n+1, 0);
for(int i = 1; i <= n; ++i) {
cin >> a[i];
pr[i] = pr[i-1] + a[i]; // clearer prefix sum
}
map<int, int> mp;
// use n+2 sized jump to safely index up to n+1
vector<vector<int>> jump(21, vector<int>(n+2, -1));
// initialize all to -1 (already done)
jump[0][n] = n + 1;
mp[pr[n]] = n;
int pos_zero = n+1;
if(a[n] == 0) pos_zero = n;
for(int i = n - 1; i >= 1; --i) {
if (mp.find(pr[i-1]) == mp.end()) jump[0][i] = min(jump[0][i+1], pos_zero);
else {
jump[0][i] = min({jump[0][i+1], mp[pr[i-1]], pos_zero});
}
// debug(i, mp[i], jump[0][i]);
if(a[i] == 0) pos_zero = i;
mp[pr[i]] = i;
}
// build binary lifting table
for(int j = 1; j <= 20; ++j) {
for(int i = 1; i <= n; ++i) {
if (jump[j-1][i] != -1) {
int nxt = jump[j-1][i];
jump[j][i] = (nxt <= n+1) ? jump[j-1][nxt] : -1;
}
}
}
// for(int i=1; i<=n; i++) {
// debug(i);
// debug(jump[0][i], jump[1][i], jump[2][i]);
// }
int q;
cin >> q;
while(q--) {
int l, r;
cin >> l >> r;
int cur = l, ans = a[cur] == 0;
// debug(cur);
for(int j = 20; j >= 0; --j) {
// debug(cur, j, jump[j][cur]);
if (jump[j][cur] != -1 && jump[j][cur] <= r) {
ans += (1LL << j);
cur = jump[j][cur];
}
}
cout << ans << '\n';
}
}
// ----------- Main Function ------------
int32_t main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t = 1;
// cin >> t;
for(int i = 1; i <= t; ++i) {
solve();
}
return 0;
}
