//#pragma GCC optimize("O3") #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> using namespace std; using namespace __gnu_pbds; typedef tree<int, null_type, std::greater<int>, rb_tree_tag, tree_order_statistics_node_update> indexed_set; typedef tree<long long, null_type, less_equal<>, rb_tree_tag, tree_order_statistics_node_update> ordered_multiset; #define rep(a, b, c, d) for (int a = b; a < c; a += d) #define INF ((1ll << 55) - 1) #define all(x) (x).begin(), (x).end() #define sz(x) ((int)(x).size()) #define uint unsigned long long #define fastio cin.tie(0), ios_base::sync_with_stdio(false); #define mi double #define ld double #define sq(x) ((x) * (x)) #define int long long #define double long double int bp[300005][19]; vector<int> v; int n; int get(int ind) { if (ind < 0 || ind >= n) return -INF; return v[ind]; } void init(int ind) { bp[ind][0] = bp[ind + 1][0]; int cs = 0; for (int i = ind; i < bp[ind][0]; ++i) { cs += v[i]; if (cs > get(ind - 1) && cs > get(i + 1)) { bp[ind][0] = i; break; } } for (int i = 1; i < 19; ++i) { bp[ind][i] = bp[bp[ind][i - 1] + 2][i - 1]; } } void build() { for (int i = 0; i < 19; ++i) { bp[n][i] = bp[n + 1][i] = bp[n + 2][i] = n; } for (int i = n - 1; i >= 0; --i) { init(i); } } int solve2(int l, int r) { if (l > r) return -INF; l++; int result = 0; for (int i = 18; i >= 0; --i) { if (bp[l][i] < r) { result += (1ll << i); l = bp[l][i] + 2; } } return result * 2 + 1; } int solve(int l, int r) { int result = 1; int pl = l; { int cs = 0; while (pl < n) { cs += v[pl]; if (cs > get(pl + 1)) break; pl++; } } int pr = r; { int cs = 0; while (pr >= 0) { cs += v[pr]; if (cs > get(pr - 1)) break; pr--; } } result = max(result, solve2(l, r)); result = max(result, solve2(pl + 1, pr - 1) + 2); result = max(result, solve2(pl + 1, r) + 1); result = max(result, solve2(l, pr - 1) + 1); return result; } auto main() -> signed { fastio; cin >> n; v.resize(n); for (auto& i : v) cin >> i; build(); int q; cin >> q; while (q--) { int x, y; cin >> x >> y; x--; int te = v[x]; v[x] = y; if (te != y) build(); int l, r; cin >> l >> r; r--; cout << solve(l, r) << '\n'; } }