#include <bits/stdc++.h>
using namespace std;
const int inf = 1e9;
class segment_tree {
int n;
vector<int> seg;
public:
segment_tree(int n) : n(n), seg(2 * n, -inf) {}
void set(int i, int x) {
for (seg[i += n] = x, i >>= 1; i > 0; i >>= 1) {
seg[i] = max(seg[2 * i], seg[2 * i + 1]);
}
}
int query(int l, int r) {
int ans = -inf;
for (l += n, r += n + 1; l < r; l >>= 1, r >>= 1) {
if (l & 1) ans = max(ans, seg[l++]);
if (r & 1) ans = max(ans, seg[--r]);
}
return ans;
}
};
int solve(const vector<int> &a) {
const int n = a.size();
vector<int64_t> pa(n);
pa[0] = a[0];
for (int i = 1; i < n; ++i) {
pa[i] = pa[i - 1] + a[i];
}
// dp[i][j][0/1] = answer when last chosen subarray is [j...i]
vector dp(n, vector(n, vector<int>(2, 1)));
vector sts(n, vector(2, segment_tree(n)));
// 0 => blue
// 1 => red
for (int i = 0; i < n; ++i) {
for (int j = 0; j <= i; ++j) {
if (j == 0) {
continue;
}
if (pa[i] - pa[j - 1] < pa[j - 1]) {
dp[i][j][0] = max(dp[i][j][0], dp[j - 1][0][1] + 1);
}
if (pa[i] - pa[j - 1] > pa[j - 1]) {
dp[i][j][1] = max(dp[i][j][1], dp[j - 1][0][0] + 1);
}
int s1 = 1, e1 = lower_bound(pa.begin(), pa.end(), 2 * pa[j - 1] - pa[i]) - pa.begin();
int s2 = upper_bound(pa.begin(), pa.end(), 2 * pa[j - 1] - pa[i]) - pa.begin() + 1, e2 = j - 1;
if (s1 <= e1) {
dp[i][j][0] = max(dp[i][j][0], sts[j - 1][1].query(s1, e1) + 1);
}
if (s2 <= e2) {
dp[i][j][1] = max(dp[i][j][1], sts[j - 1][0].query(s2, e2) + 1);
}
}
for (int j = 0; j <= i; ++j) {
sts[i][0].set(j, dp[i][j][0]);
sts[i][1].set(j, dp[i][j][1]);
}
}
int ans = 0;
for (int j = 0; j <= n - 1; ++j) {
for (int k = 0; k < 2; ++k) {
ans = max(ans, dp[n - 1][j][k]);
}
}
return ans;
}
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
int n;
cin >> n;
vector<int> l(n);
for (int &i : l) {
cin >> i;
}
int q;
cin >> q;
while (q--) {
int x, y, a, b;
cin >> x >> y >> a >> b;
l[x - 1] = y;
vector<int> vec;
for (int i = a; i < b; ++i) {
vec.push_back(l[i]);
}
cout << solve(vec) << '\n';
}
}
