// prefix add / 末尾追加 / 全体 max
// https://qoj.ac/contest/1472/problem/7905
struct Prefix_Add_Append_Get_Max {
  int n;
  UnionFind uf;
  vc<pair<int, int>> range;
  vi dat;
  ll max;
  Prefix_Add_Append_Get_Max(int max_n) : n(max_n), uf(max_n), range(max_n), max(-infty<ll>) {}

  void append(int i, ll x) {
    assert(i == len(dat) && i < n);
    range[i] = {i, i + 1};
    if (i == 0) {
      max = x;
      dat.eb(x);
      return;
    }
    if (x > max) {
      dat.eb(x - max);
      max = x;
      return;
    }
    dat.eb(0);
    merge(i);
    return;
  }

  void merge(int i) {
    int a = uf[i - 1], b = uf[i];
    assert(a != b);
    uf.merge(a, b);
    int c = uf[a];
    range[c].fi = range[a].fi, range[c].se = range[b].se;
  }

  // [0,i), +x
  void prefix_add(int i, ll x) {
    if (i == 0) return;
    assert(i <= len(dat) && x >= 0);
    dat[0] += x, max += x;
    while (x > 0) {
      auto [l, r] = range[uf[i]];
      int p = (l == i ? l : r);
      if (p == len(dat)) return;
      ll y = dat[p];
      ll z = min(x, y);
      dat[p] -= z, x -= z, max -= z;
      if (dat[p] == 0) {
        merge(p);
        continue;
      }
    }
  }

  ll get_max() { return max; }
};

answer.code:5:3: error: ‘UnionFind’ does not name a type
    5 |   UnionFind uf;
      |   ^~~~~~~~~
answer.code:6:6: error: ‘pair’ was not declared in this scope
    6 |   vc<pair<int, int>> range;
      |      ^~~~
answer.code:6:6: error: ‘pair’ was not declared in this scope
answer.code:6:6: error: ‘pair’ was not declared in this scope
answer.code:6:6: error: ‘pair’ was not declared in this scope
answer.code:6:6: error: ‘pair’ was not declared in this scope
answer.code:6:6: error: ‘pair’ was not declared in this scope
answer.code:6:6: error: ‘pair’ was not declared in this scope
answer.code:6:6: error: ‘pair’ was not declared in this scope
answer.code:6:6: error: ‘pair’ was not declared in this scope
answer.code:6:6: error: ‘pair’ was not declared in this scope
answer.code:6:3: error: ‘vc’ does not name a type
    6 |   vc<pair<int, int>> range;
      |   ^~
answer.code:7:3: error: ‘vi’ does not name a type; did you mean ‘void’?
    7 |   vi dat;
      |   ^~
      |   void
answer.code:8:3: error: ‘ll’ does not name a type
    8 |   ll max;
      |   ^~
answer.code:11:22: error: ‘ll’ has not been declared
   11 |   void append(int i, ll x) {
      |                      ^~
answer.code:38:26: error: ‘ll’ has not been declared
   38 |   void prefix_add(int i, ll x) {
      |                          ^~
answer.code:56:3: error: ‘ll’ does not name a type
   56 |   ll get_max() { return max; }
      |   ^~
answer.code: In constructor ‘Prefix_Add_Append_Get_Max::Prefix_Add_Append_Get_Max(int)’:
answer.code:9:52: error: class ‘Prefix_Add_Append_Get_Max’ does not have any field named ‘uf’
    9 |   Prefix_Add_Append_Get_Max(int max_n) : n(max_n), uf(max_n), range(max_n), max(-infty<ll>) {}
      |                                                    ^~
answer.code:9:63: error: class ‘Prefix_Add_Append_Get_Max’ does not have any field named ‘range’
    9 |   Prefix_Add_Append_Get_Max(int max_n) : n(max_n), uf(max_n), range(max_n), max(-infty<ll>) {}
      |                                                               ^~~~~
answer.code:9:77: error: class ‘Prefix_Add_Append_Get_Max’ does not have any field named ‘max’
    9 |   Prefix_Add_Append_Get_Max(int max_n) : n(max_n), uf(max_n), range(max_n), max(-infty<ll>) {}
      |                                                                             ^~~
answer.code:9:88: error: ‘ll’ was not declared in this scope
    9 |   Prefix_Add_Append_Get_Max(int max_n) : n(max_n), uf(max_n), range(max_n), max(-infty<ll>) {}
      |                                                                                        ^~
answer.code:9:82: error: ‘infty’ was not declared in this scope; did you mean ‘int’?
    9 |   Prefix_Add_Append_Get_Max(int max_n) : n(max_n), uf(max_n), range(max_n), max(-infty<ll>) {}
      |                                                                                  ^~~~~
      |                                                                                  int
answer.code:9:91: error: expected primary-expression before ‘)’ token
    9 |   Prefix_Add_Append_Get_Max(int max_n) : n(max_n), uf(max_n), range(max_n), max(-infty<ll>) {}
      |                                                                                           ^
answer.code: In member function ‘void Prefix_Add_Append_Get_Max::append(int, int)’:
answer.code:12:21: error: ‘dat’ was not declared in this scope
   12 |     assert(i == len(dat) && i < n);
      |                     ^~~
answer.code:12:17: error: ‘len’ was not declared in this scope
   12 |     assert(i == len(dat) && i < n);
      |                 ^~~
answer.code:12:5: error: ‘assert’ was not declared in this scope
   12 |     assert(i == len(dat) && i < n);
      |     ^~~~~~
answer.code:1:1: note: ‘assert’ is defined in header ‘<cassert>’; did you forget to ‘#include <cassert>’?
  +++ |+#include <cassert>
    1 | // prefix add / 末尾追加 / 全体 max
answer.code:13:5: error: ‘range’ was not declared in this scope
   13 |     range[i] = {i, i + 1};
      |     ^~~~~
answer.code:15:7: error: ‘max’ was not declared in this scope
   15 |       max = x;
      |       ^~~
answer.code:19:13: error: ‘max’ was not declared in this scope
   19 |     if (x > max) {
      |             ^~~
answer.code: In member function ‘void Prefix_Add_Append_Get_Max::merge(int)’:
answer.code:30:13: error: ‘uf’ was not declared in this scope
   30 |     int a = uf[i - 1], b = uf[i];
      |             ^~
answer.code:31:17: error: ‘b’ was not declared in this scope
   31 |     assert(a != b);
      |                 ^
answer.code:31:5: error: ‘assert’ was not declared in this scope
   31 |     assert(a != b);
      |     ^~~~~~
answer.code:31:5: note: ‘assert’ is defined in header ‘<cassert>’; did you forget to ‘#include <cassert>’?
answer.code:34:5: error: ‘range’ was not declared in this scope
   34 |     range[c].fi = range[a].fi, range[c].se = range[b].se;
      |     ^~~~~
answer.code: In member function ‘void Prefix_Add_Append_Get_Max::prefix_a...