#include <bits/stdc++.h>
#define int long long
using namespace std;
const int inf = 1e9 + 7, maxn = 2e5 + 5;
int st[4*maxn + 5];
void build(int id, int l, int r, vector<int> &a){
if (l == r){
st[id] = a[l];
return;
}
int mid = (l + r)/2;
build(id*2, l, mid, a);
build(id*2+1, mid+1, r, a);
st[id] = min(st[id*2], st[id*2+1]);
}
int get(int id, int l, int r, int ul, int ur){
if (l > ur || r < ul) return inf;
if (ul <= l && r <= ur) return st[id];
int mid = (l + r)/2;
return min(get(id*2, l, mid, ul, ur), get(id*2+1, mid+1, r, ul, ur));
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(nullptr);
int n, q;
cin >> n;
vector<int> a(n+1, 0);
for (int i = 1; i <= n; i++){
cin >> a[i];
}
cin >> q;
if (q <= 20){
// do regretful greedy
for (int j = 0; j < q; j++){
int l, r;
cin >> l >> r;
priority_queue<int> pq;
pq.push(-inf);
int cur = 0, ans = 0;
for (int i = l; i <= r; i++){
if (cur >= a[i]){
cur -= a[i];
pq.push(a[i]);
ans++;
}
else{
// check if can untake largest one
int tp = pq.top();
if (a[i] < tp){
// then take;
cur += 2*tp - a[i];
pq.pop();
pq.push(a[i]);
}
else{
cur += a[i];
}
}
}
cout << ans << "\n";
}
}
else{
// do rmq
vector<int> diff(n+2, 0), pref(n+1, 0);
pref[0] = 0;
for (int i = 1; i <= n; i++){
pref[i] = pref[i-1] + (a[i] == 1);
}
diff[1] = 0;
for (int i = 2; i <= n+1; i++){
diff[i] = diff[i-1] + ((a[i-1] > 1) ? a[i-1] : -a[i-1]);
}
int terminus = n + 1;
build(1, 1, terminus, diff);
for (int j = 0; j < q; j++){
int l, r;
cin >> l >> r;
int offset = diff[l], end = diff[r+1] - offset, ans = pref[r] - pref[l-1];
int mn = get(1, 1, terminus, l, r + 1) - offset;
if (mn < 0){
// find min o
int rev = -mn, add = rev/2 + (rev % 2);
ans -= add;
end += 2*add;
}
cout << ans + (end / 4) << "\n";
}
}
return 0;
}
