#include<bits/stdc++.h>
#define taskname "C"
using namespace std;
template<class T>void maximize(T& a, T b){
if(a < b){
a = b;
}
}
const int lim = 2e5 + 3;
int n, q, a[lim];
namespace sub12{
void solve(){
for(int _ = 0; _ < q; _++){
int l, r;
cin >> l >> r;
vector<int>f(1, 0);
for(int i = l; i <= r; i++){
vector<int>nf(f.size() + a[i], 0);
for(int j = 0; j < f.size(); j++){
nf[j + a[i]] = f[j];
}
for(int j = a[i]; j < f.size(); j++){
maximize(nf[j - a[i]], f[j] + 1);
}
swap(f, nf);
}
cout << *max_element(f.begin(), f.end()) << "\n";
}
}
}
namespace sub3{
const int lim = 5e3 + 5;
int f[lim];
void solve(){
for(int _ = 0; _ < q; _++){
int l, r;
cin >> l >> r;
memset(f, -0x0f, sizeof(f));
f[0] = 0;
for(int i = l; i <= r; i++){
for(int j = i - l; j > 0; j--){
if(f[j] > -1){
f[j] += a[i];
}
if(f[j - 1] >= a[i]){
maximize(f[j], f[j - 1] - a[i]);
}
}
f[0] += a[i];
}
for(int i = r - l; i > -1; i--){
if(f[i] > -1){
cout << i << "\n";
break;
}
}
}
}
}
namespace sub4{
vector<int>st, lazy;
void propagate(int id, int x){
st[id] += x;
lazy[id] += x;
}
void push_down(int id){
propagate(id << 1, lazy[id]);
propagate(id << 1 | 1, lazy[id]);
lazy[id] = 0;
}
void update(int id, int l, int r, int u, int v, int x){
if(l > v || r < u){
return;
}
if(u <= l && v >= r){
propagate(id, x);
return;
}
int m = (l + r) >> 1;
push_down(id);
update(id << 1, l, m, u, v, x);
update(id << 1 | 1, m + 1, r, u, v, x);
st[id] = min(st[id << 1], st[id << 1 | 1]);
}
void solve(){
st.resize(n << 2 | 3);
lazy.resize(n << 2 | 3);
for(int _ = 0; _ < q; _++){
int l, r, ans = 0;
cin >> l >> r;
fill(st.begin(), st.end(), 0);
fill(lazy.begin(), lazy.end(), 0);
for(int i = l; i <= r; i++){
update(1, 1, n, i, r, a[i]);
}
vector<int>p(r - l + 1);
iota(p.begin(), p.end(), l);
sort(p.begin(), p.end(), [&] (int i, int j){
return a[i] < a[j] || (a[i] == a[j] && i > j);
});
for(int& i : p){
update(1, 1, n, i, r, -(a[i] << 1));
if(st[1] < 0){
update(1, 1, n, i, r, a[i] << 1);
}
else{
ans++;
}
}
cout << ans << "\n";
}
}
}
namespace sub567{
const int LIM = 102;
const int LG = 18;
int pf[lim], df[lim], lgv[lim], ans[lim], cnt[lim], start_low[lim], delta[lim], spt[LG][lim];
pair<int, int>query[lim];
int get(int l, int r){
int k = lgv[r - l + 1];
return min(spt[k][l], spt[k][r - (1 << k) + 1]);
}
void solve(){
lgv[pf[0] = 0] = -1;
for(int i = 1; i <= n; i++){
pf[i] = pf[i - 1] + a[i];
lgv[i] = lgv[i >> 1] + 1;
}
for(int i = 1; i <= n; i++){
cin >> query[i].first >> query[i].second;
start_low[i] = query[i].first;
}
memset(ans, 0, sizeof(ans));
memset(delta, 0, sizeof(delta));
for(int x = 1; x < LIM; x++){
memset(cnt, 0, sizeof(cnt));
memset(df, 0, sizeof(df));
for(int i = 1; i <= n; i++){
if(a[i] <= x){
df[i] += a[i];
if(a[i] == x){
cnt[i]++;
}
}
}
for(int i = 1; i <= n; i++){
spt[0][i] = pf[i] - ((df[i] += df[i - 1]) << 1);
cnt[i] += cnt[i - 1];
}
for(int i = 1; i < LG; i++){
for(int j = 1; j + (1 << i) - 1 <= n; j++){
spt[i][j] = min(spt[i - 1][j], spt[i - 1][j + (1 << (i - 1))]);
}
}
for(int qid = 1; qid <= q; qid++){
auto& [l, r] = query[qid];
int low = start_low[qid], high = r, pos = r + 1;
while(low <= high){
int mid = (low + high) >> 1;
if(get(mid, r) - pf[l - 1] + cnt[mid - 1] * (x << 1) + delta[qid] > -1){
high = (pos = mid) - 1;
}
else{
low = mid + 1;
}
}
ans[qid] += cnt[r] - cnt[(start_low[qid] = pos) - 1];
delta[qid] += cnt[pos - 1] * (x << 1);
}
}
for(int i = 1; i <= q; i++){
cout << ans[i] << "\n";
}
}
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
if(fopen(taskname".inp", "r")){
freopen(taskname".inp", "r", stdin);
}
cin >> n;
for(int i = 1; i <= n; i++){
cin >> a[i];
}
cin >> q;
if(n <= 300 && q <= 20){
sub12::solve();
}
else if(n <= 5000 && q <= 20){
sub3::solve();
}
else if(q <= 20){
sub4::solve();
}
else{
sub567::solve();
}
}
