#include <bits/stdc++.h>
using namespace std;
#define long long long
const int MAXN = 250005;
const int LOG = 19;
const long INF = 1e18;
int N, Q;
long L[MAXN];
long P[MAXN]; // Prefix sum
// Segment Tree để tìm chỉ số j nhỏ nhất thỏa mãn điều kiện 2
long tree[4 * MAXN];
void build(int node, int start, int end) {
if (start == end) {
// Lưu giá trị P[start-1] - d[start]
// Lưu ý: start là index mảng d (1-based)
tree[node] = P[start - 1] - L[start];
} else {
int mid = (start + end) / 2;
build(2 * node, start, mid);
build(2 * node + 1, mid + 1, end);
tree[node] = max(tree[2 * node], tree[2 * node + 1]);
}
}
// Tìm chỉ số nhỏ nhất trong đoạn [l, r] có giá trị > val
int query_first(int node, int start, int end, int l, int r, long val) {
// Nếu đoạn không giao hoặc max value không đủ lớn
if (start > end || start > r || end < l || tree[node] <= val) {
return -1;
}
if (start == end) {
return start;
}
int mid = (start + end) / 2;
// Ưu tiên tìm bên trái trước (để lấy chỉ số nhỏ nhất)
int res = query_first(2 * node, start, mid, l, r, val);
if (res != -1) return res;
return query_first(2 * node + 1, mid + 1, end, l, r, val);
}
int nxt[MAXN]; // Next valley index
int up[MAXN][LOG]; // Binary lifting table
// Hàm tính số bước nhảy từ u nhưng không vượt quá r
// Trả về số lượng mảnh *thêm vào* sau mảnh u
int calc_steps(int u, int r) {
if (u > r) return 0;
int steps = 0;
int curr = u;
// Nhảy doubling
for (int k = LOG - 1; k >= 0; k--) {
if (up[curr][k] <= r && up[curr][k] != N + 2) {
curr = up[curr][k];
steps += (1 << k);
}
}
// steps tính số cặp (Peak, Valley).
// Tổng số mảnh từ u đến curr là 1 (u) + 2 * steps.
int pieces = 2 * steps;
// Kiểm tra xem có thể tạo thêm 1 Đỉnh cuối cùng từ curr đến r không
// Điều kiện: Sum(curr+1...r) > d[curr]
if (P[r] - P[curr] > L[curr]) {
pieces++;
}
return pieces;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
if (!(cin >> N)) return 0;
for (int i = 1; i <= N; i++) {
cin >> L[i];
P[i] = P[i - 1] + L[i];
}
build(1, 1, N);
// Precompute next valley for every i
for (int i = 1; i <= N; i++) {
long val1 = P[i] + L[i];
// Tìm k nhỏ nhất sao cho P[k] > P[i] + L[i]
int k = upper_bound(P + 1, P + N + 1, val1) - P;
// Cần tìm j >= k+1 sao cho P[j-1] - L[j] > P[i]
int start_search = k + 1;
int target_j = -1;
if (start_search <= N) {
target_j = query_first(1, 1, N, start_search, N, P[i]);
}
if (target_j != -1) {
nxt[i] = target_j;
} else {
nxt[i] = N + 2; // Vô cực
}
}
// Build Doubling Table
// nxt[i] nhảy từ thung lũng i đến thung lũng tiếp theo (bỏ qua 1 đỉnh ở giữa)
for (int i = 1; i <= N; i++) up[i][0] = nxt[i];
for (int i = 0; i < LOG; i++) up[N + 1][i] = N + 2;
for (int i = 0; i < LOG; i++) up[N + 2][i] = N + 2;
for (int k = 1; k < LOG; k++) {
for (int i = 1; i <= N; i++) {
if (up[i][k - 1] <= N) {
up[i][k] = up[up[i][k - 1]][k - 1];
} else {
up[i][k] = N + 2;
}
}
}
cin >> Q;
while (Q--) {
int X, A, B;
long Y;
cin >> X >> Y >> A >> B;
// Subtask 4: Y = L[X], bỏ qua update, chỉ query
int l = A + 1;
int r = B;
if (l > r) { // Trường hợp rỗng (không thể xảy ra theo đề bài A < B nhưng đề phòng)
cout << 0 << "\n";
continue;
}
// Cách 1: Bắt đầu bằng Thung lũng tại l
// Độ dài = 1 (thung lũng l) + các bước nhảy
int ans1 = 1 + calc_steps(l, r);
// Cách 2: Bắt đầu bằng Đỉnh.
// Ta cần tìm thung lũng đầu tiên j > l sao cho Đỉnh [l...j-1] > d[j]
// Tức là tìm j nhỏ nhất thuộc [l+1, r] sao cho P[j-1] - d[j] > P[l-1]
int first_valley = query_first(1, 1, N, l + 1, r, P[l - 1]);
int ans2 = 0;
if (first_valley != -1) {
// Độ dài = 1 (Đỉnh đầu tiên) + 1 (thung lũng first_valley) + các bước nhảy
ans2 = 2 + calc_steps(first_valley, r);
} else {
// Nếu không tìm được thung lũng nào để kết thúc cái đỉnh đầu tiên
// Thì toàn bộ đoạn [l, r] là 1 đỉnh (hoặc 1 mảnh)
ans2 = 1;
}
cout << max(ans1, ans2) << "\n";
}
return 0;
}
