#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int n,a[400005],q;
ll sp[400005];
int p4[10];
int unde[10][400005];
const int MOD = 10017;
vector<pair<ll,int>> v[MOD + 5];
int inf = 2e9;
int ce(ll val)
{
int ret = inf;
for (auto it : v[val % MOD])
if (it.first == val)
ret = it.second;
if (ret == inf)
return 0;
return ret;
}
void set_nxt_sp(ll x,int tr)
{
v[x % MOD].push_back({x,tr});
}
void build()
{
unde[0][n + 1] = n + 1;
for (int i = n; i >= 1; i--)
{
set_nxt_sp(sp[i],i);
int x = ce(sp[i - 1]);
if (x == 0)
x = n + 1;
unde[0][i] = min(x,unde[0][i + 1]);
}
for (int j = 1; j <= 9; j++)
{
unde[j][n + 1] = n + 1;
for (int i = 1; i <= n; i++)
{
int pz = i;
for (int q = 1; q <= 3; q++)
{
pz = unde[j - 1][pz] + 1;
if (pz > n + 1)
pz = n + 1;
}
unde[j][i] = unde[j - 1][pz];
}
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> n;
for (int i = 1; i <= n; i++)
cin >> a[i],sp[i] = sp[i - 1] + a[i];
p4[0] = 1;
for (int i = 1; i <= 9; i++)
p4[i] = 4 * p4[i - 1];
build();
cin >> q;
for (int i = 1; i <= q; i++)
{
int l,r;
cin >> l >> r;
int ans = 0;
int p = l;
for (int pas = 9; pas >= 0; pas--)
{
while (unde[pas][p] <= r)
{
ans += p4[pas];
p = unde[pas][p] + 1;
}
}
cout << ans << '\n';
}
return 0;
}
