gss.cpp

#include <bits/stdc++.h>
using namespace std;

#define taskname "gss"

// typedef long long ll;
#define int long long

void ioset() {
  cin.tie(0)->sync_with_stdio(0);
  if (fopen(taskname".in", "r")) {
    freopen(taskname".in", "r", stdin);
    // freopen(taskname".out", "w", stdout);
  }
}

const int INF = 0x3f3f3f3f;

template<typename T>
bool chmax(T &a, T b) {
  return a < b ? a = b, true : false;
}

struct Data {
  int sum, max, maxl, maxr;
  Data() { sum = max = maxl = maxr = -INF; }
  Data(int x) { sum = max = maxl = maxr = x; }
};

struct Node {
  Data data;
  Node *lef, *rig;
  Node() { lef = rig = nullptr; }
};

struct SMT {
  int n; Node *node;
  Data merge(Data lef, Data rig) {
    Data node;
    node.sum  = lef.sum + rig.sum;
    node.maxl = max(lef.maxl, lef.sum + rig.maxl);
    node.maxr = max(rig.maxr, rig.sum + lef.maxr);
    node.max  = max(lef.max, rig.max);
    chmax(node.max, lef.maxr + rig.maxl);
    return node;
  }
  void build(Node *&node, int l, int r, vector<int> &a) {
    if (l > r) return;
    if (node == nullptr) node = new Node;
    if (l == r) {
      node->data = Data(a[l]);
      return;
    }
    int m = (l + r) / 2;
    build(node->lef, l, m, a);
    build(node->rig, m + 1, r, a);
    node->data = merge(node->lef->data, node->rig->data);
  }
  SMT(int n, vector<int> &a): n(n) {
    node = new Node;
    build(node, 0, n - 1, a);
  }
  Data get(Node *&node, int l, int r, int u, int v) {
    if (r < u || l > v) return Data();
    if (l >= u && r <= v) return node->data;
    int m = (l + r) / 2;
    return merge(get(node->lef, l, m, u, v), get(node->rig, m + 1, r, u, v));
  }
  Data get(int u, int v) {
    return get(node, 0, n - 1, u, v);
  }
};

void solve() {
  int n; cin >> n;
  vector<int> a(n);
  for (auto &i : a) cin >> i;
  SMT smt(n, a);
  int q; cin >> q;
  while (q--) {
    int u, v;
    cin >> u >> v;
    u--; v--;
    cout << smt.get(u, v).max << '\n';
  }
}

signed main() {
  ioset();
  solve();
}