#include <bits/stdc++.h> using namespace std; using ll = long long; int main(){ int n;cin>>n; vector<int> A(n); for(int &i:A) cin>>i; int q;cin>>q; vector<pair<int, int>> Q(q); for(int i=0;i<q;i++){ cin>>Q[i].first>>Q[i].second; } vector<ll> pref(n+1); for(int i=0;i<n;i++){ pref[i+1] = pref[i] + A[i]; } vector<int> next(n+1); map<ll, int> lasts; for(int i=n;i>=0;i--){ if(lasts.count(pref[i]) == 0){ next[i] = n+1; } else{ next[i] = lasts[pref[i]]; } lasts[pref[i]] = i; } for(int i=0;i<q;i++){ vector<int> mns(n+1); int a = Q[i].first, b = Q[i].second; mns[b] = 0; for(int j=b-1; j>=a-1; j--){ if(next[j] > b) mns[j] = max(mns[j+1], 0); else mns[j] = max(mns[j+1], mns[next[j]]+1); } // for(ll i:mns) // cout << i << ' '; // cout << '\n'; cout << mns[a-1] << '\n'; } }