/*
Author: Nguyen Chi Thanh - High School for the Gifted - VNU.HCM (i2528)
*/
#include "secret.h"
#include <bits/stdc++.h>
using namespace std;
#ifdef NCTHANH
// Copied from sample grader
const int MAX_VALUE = 1000000000;
int query_count = 0;
int Secret(int X, int Y) {
++query_count;
if (!(0 <= X && X <= MAX_VALUE)) {
fprintf(stderr, "Wrong Answer [1]\n");
exit(0);
}
if (!(0 <= Y && Y <= MAX_VALUE)) {
fprintf(stderr, "Wrong Answer [1]\n");
exit(0);
}
return (X + 2 * (Y / 2) < MAX_VALUE) ? (X + 2 * (Y / 2)) : MAX_VALUE;
}
#endif
const int MAXN = 1005;
const int LG = 10;
int n, a[MAXN], info[LG + 1][MAXN];
void dnc(int l, int r, int level) {
if (l == r) return;
int mid = (l + r) >> 1;
info[level][mid] = a[mid];
for (int i = mid - 1; i >= l; --i)
info[level][i] = Secret(a[i], info[level][i + 1]);
info[level][mid + 1] = a[mid + 1];
for (int i = mid + 2; i <= r; ++i)
info[level][i] = Secret(info[level][i - 1], a[i]);
dnc(l, mid, level + 1);
dnc(mid + 1, r, level + 1);
return;
}
void Init(int N, int A[]) {
n = N;
for (int i = 1; i <= n; ++i) a[i] = A[i - 1];
dnc(1, n, 1);
return;
}
int Query(int l, int r) {
++l; ++r;
if (l == r) return a[l];
int curL = 1, curR = n, level = 1;
while (true) {
int mid = (curL + curR) >> 1;
if (l <= mid && r > mid)
return Secret(info[level][l], info[level][r]);
if (r <= mid) curR = mid;
else curL = mid + 1;
++level;
}
}
#ifdef NCTHANH
int N, Q, A[MAXN];
signed main() {
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
ios_base::sync_with_stdio(0);
cin.tie(nullptr); cout.tie(nullptr);
cin >> N;
for (int i = 0; i < N; ++i) cin >> A[i];
Init(N, A);
cin >> Q;
for (int i = 0; i < Q; ++i) {
int l, r; cin >> l >> r;
cout << Query(l, r) << '\n';
}
return 0;
}
#endif
