#include using namespace std; // Define using ll = long long; using ull = unsigned long long; using ld = long double; const ll dx[4] = {1, 0, -1, 0}; const ll dy[4] = {0, 1, 0, -1}; const ll MOD = 1e9 + 7; const ll mod = 998244353; const ll inf = 1 << 30; const ll LINF = LONG_MAX; const ll INF = 1LL << 60; const ull MAX = ULONG_MAX; #define mp make_pair #define pb push_back #define elif else if #define endl '\n' #define space ' ' #define def inline auto #define func inline constexpr ll #define run(a) __attribute__((constructor)) def _##a() #define all(v) begin(v), end(v) #define rall(v) rbegin(v), rend(v) #define input(a) scanf("%lld", &(a)) #define print(a) printf("%lld\n", (a)) #define fi first #define se second #define ok(a, b) (0 <= (a) && (a) < (b)) template using vvector = vector>; template using pvector = vector>; template using rpriority_queue = priority_queue, greater>; template bool chmax(T &a, const T &b) { if (a < b) { a = b; return 1; } return 0; } template bool chmin(T &a, const T &b) { if (a > b) { a = b; return 1; } return 0; } // Debug #define debug(...) \ { \ cerr << __LINE__ << ": " << #__VA_ARGS__ << " = "; \ for (auto &&X : {__VA_ARGS__}) cerr << "[" << X << "] "; \ cerr << endl; \ } #define dump(a, h, w) \ { \ cerr << __LINE__ << ": " << #a << " = [" << endl; \ rep(__i, h) { \ rep(__j, w) { cerr << a[__i][__j] << space; } \ cerr << endl; \ } \ cerr << "]" << endl; \ } #define vdump(a, n) \ { \ cerr << __LINE__ << ": " << #a << " = ["; \ rep(__i, n) if (__i) cerr << space << a[__i]; \ else cerr << a[__i]; \ cerr << "]" << endl; \ } // Loop #define inc(i, a, n) for (ll i = (a), _##i = (n); i <= _##i; ++i) #define dec(i, a, n) for (ll i = (a), _##i = (n); i >= _##i; --i) #define rep(i, n) for (ll i = 0, _##i = (n); i < _##i; ++i) #define each(i, a) for (auto &&i : a) #define loop() for (;;) // Stream #define fout(n) cout << fixed << setprecision(n) #define fasten cin.tie(0), ios::sync_with_stdio(0) run(0) { fasten, fout(10); } // Speed #pragma GCC optimize("O3") #pragma GCC target("avx") // Math func gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; } func lcm(ll a, ll b) { return a * b / gcd(a, b); } func sign(ll a) { return a ? abs(a) / a : 0; } inline constexpr ll modulo(const ll n, const ll m = MOD) { ll k = n % m; return k + m * (k < 0); } inline constexpr ll chmod(ll &n, const ll m = MOD) { n %= m; return n += m * (n < 0); } inline constexpr ll mpow(ll a, ll n, const ll m = MOD) { ll r = 1; while (n) { if (n & 1) r *= a; chmod(r, m); a *= a; chmod(a, m); n >>= 1; } return r; } inline ll inv(const ll n, const ll m) { ll a = n, b = m, x = 1, y = 0; while (b) { ll t = a / b; a -= t * b; swap(a, b); x -= t * y; swap(x, y); } return x % m; } struct Factor { inline vector factors(ll N) { vector A; ll i = 2; while (i * i <= N) { if (N % i == 0) { A.push_back(i); N /= i; } else { i++; } } if (N != 1) A.push_back(N); sort(all(A)); return A; } inline vector divisor(ll N) { vector A = factors(N), B; ll a = A.size(); rep(i, 1 << a) { ll d = 1; rep(j, a) if (i & (1 << j)) d *= A[j]; B.push_back(d); } sort(all(B)), B.erase(unique(all(B)), B.end()); return B; } }; struct csum { ll N; vector A, S; csum(vector v) : A(v), S(1) { each(k, v) S.push_back(k + S.back()); } ll sum(ll l, ll r) { return S[r] - S[l]; } ll lsum(ll r) { return S[r]; } ll rsum(ll l) { return S.back() - S[l]; } }; struct RUMQ { #define INF 0 #define min max static const ll n = 1LL << 20; vector node, lazy, flag; RUMQ() : node(n * 2 - 1), lazy(n * 2 - 1), flag(n * 2 - 1) {} inline void eval(ll i, ll l, ll r) { if (flag[i]) { node[i] = lazy[i]; if (r - l > 1) { lazy[i * 2 + 1] = lazy[i * 2 + 2] = lazy[i]; flag[i * 2 + 1] = flag[i * 2 + 2] = true; } lazy[i] = 0; flag[i] = false; } } inline void update(ll a, ll b, ll x, ll i = 0, ll l = 0, ll r = 1LL << 20) { eval(i, l, r); if (b <= l || r <= a) return; if (a <= l && r <= b) { lazy[i] = x; flag[i] = true; eval(i, l, r); } else { update(a, b, x, i * 2 + 1, l, (l + r) / 2); update(a, b, x, i * 2 + 2, (l + r) / 2, r); node[i] = std::min(node[i * 2 + 1], node[i * 2 + 2]); } } inline ll min(ll a, ll b, ll i = 0, ll l = 0, ll r = 1LL << 20) { if (b <= l || r <= a) return INF; eval(i, l, r); if (a <= l && r <= b) return node[i]; return std::min(min(a, b, i * 2 + 1, l, (l + r) / 2), min(a, b, i * 2 + 2, (l + r) / 2, r)); } #undef INF #undef min }; signed main() { ll N; cin >> N; ll A[N], Q, T, V; RUMQ seg; rep(i, N) { cin >> A[i]; rep(j, 24) { seg.update(i + j, i + j + 1, seg.max(i + j, i + j + 1) + A[i]); } } cin >> Q; rep(i, Q) { cin >> T >> V; rep(j, 24) { seg.update(T + j - 1, T + j, seg.max(T + j - 1, T + j) - A[T - 1] + V); } cout << seg.max(23, N) << endl; A[T - 1] = V; } }