#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];
unordered_map<ll,int> nxt_sp;
void build()
{
unde[0][n + 1] = n + 1;
for (int i = n; i >= 1; i--)
{
nxt_sp[sp[i]] = i;
int x = nxt_sp[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;
}
