Ta nhận thấy nếu sức chịu đựng ban đầu là ~x~ thoả mãn thì ~x + 1~ cũng thoả mãn. Ta sẽ chặt nhị phân đáp án ~x~ và kiểm tra xem đáp án ~x~ có thoả mãn hay không.

Ta sẽ hợp nhất các phần tử thành một đoạn liên tiếp nếu tồn tại một vị trí, mà xuất phát từ nó sẽ ăn được toàn bộ các miếng pizza. Giả sử có hai đoạn kề nhau ~[l1, r1]~ và ~[l2, r2]~ với ~r1~ kề ~l2~. Giả sử đoạn ~[l1, r1]~ đã được xét rồi và mở rộng tối đa, đoạn ~[l2, r2]~ ta đang xét. Gọi tổng độ cay đoạn ~[l1, r1]~ là ~s~. Vì đoạn ~[l1, r1]~ mở rộng tối đa nên ~x + s < a_{l2}~. Nghĩa là sau khi ăn miếng pizza ~l2~, ta luôn có sức chịu đựng lớn hơn mọi phần tử trong đoạn ~[l1, r1]~. Do đó đoạn ~[l2, r2]~ sẽ hợp nhất được với đoạn ~[l1, r1]~.

Nhờ nhận xét trên, ta có cách làm là loang lần lượt các vị trí ~i~ có ~a_i \le x~ sang hai bên. Ta sẽ lưu lại đoạn ~[l, r]~ của việc loang. Gặp những phần tử nào đã trong một đoạn trước đó rồi thì ta chỉ việc cộng vào đáp án tổng của đoạn đó chứ không loang tiếp.

Độ phức tạp ~O(n \log(max(a)))~.

Code mẫu

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define print_op(...) ostream& operator<<(ostream& out, const __VA_ARGS__& u)
#define db(val) "["#val" = "<<(val)<<"] "
#define CONCAT_(x, y) x##y
#define CONCAT(x, y) CONCAT_(x, y)
#ifdef LOCAL   
#   define clog cerr << setw(__db_level * 2) << setfill(' ') << "" << setw(0)
#   define DB() debug_block CONCAT(dbbl, __LINE__)
    int __db_level = 0;
    struct debug_block {
        debug_block() { clog << "{" << endl; ++__db_level; }
        ~debug_block() { --__db_level; clog << "}" << endl; }
    };
#else
#   define clog if (0) cerr
#   define DB(...)
#endif
template<class U, class V> print_op(pair<U, V>) {
    return out << "(" << u.first << ", " << u.second << ")";
}
template<class Con, class = decltype(begin(declval<Con>()))>
typename enable_if<!is_same<Con, string>::value, ostream&>::type
operator<<(ostream& out, const Con& con) { 
    out << "{";
    for (auto beg = con.begin(), it = beg; it != con.end(); ++it)
        out << (it == beg ? "" : ", ") << *it;
    return out << "}";
}
template<size_t i, class T> ostream& print_tuple_utils(ostream& out, const T& tup) {
    if constexpr(i == tuple_size<T>::value) return out << ")"; 
    else return print_tuple_utils<i + 1, T>(out << (i ? ", " : "(") << get<i>(tup), tup); 
}
template<class ...U> print_op(tuple<U...>) {
    return print_tuple_utils<0, tuple<U...>>(out, u);
}

const int N = 5e5 + 5;

int n;
ll a[N], d[N];
int nxt[N], prv[N], take[N];

bool check(ll k) {
    for (int i = 0; i < n; ++ i) {
        nxt[i] = (i + 1) % n;
        prv[i] = (i - 1 + n) % n;
        take[i] = 0;
        d[i] = a[i];
    }
    for (int u = 0; u < n; ++ u) if (!take[u]) {
        if (k >= a[u]) {
            while (1) {
                if (prv[u] == u && nxt[u] == u) {
                    return true;
                }
                // clog << db(u) << db(d[u]) << db(nxt[u]) << db(prv[u]) << endl;
                ll c = min(a[prv[u]], a[nxt[u]]);
                if (k + d[u] < c) break;
                if (a[prv[u]] < a[nxt[u]]) {
                    // clog << db(prv[u]) << endl;
                    take[prv[u]] = 1;
                    d[u] += d[prv[u]];
                    prv[u] = prv[prv[u]];
                    nxt[prv[u]] = u;
                } else {
                    // clog << db(nxt[u]) << endl;
                    take[nxt[u]] = 1;
                    d[u] += d[nxt[u]];
                    nxt[u] = nxt[nxt[u]];
                    prv[nxt[u]] = u;
                }
            }
        }
    }
    return false;
}

void solve() {
    cin >> n;
    for (int i = 0; i < n; ++ i) {
        cin >> a[i];
    }
    ll lo = -1, hi = 1e13 + 1;
    while (hi - lo > 1) {
        ll mid = (lo + hi) >> 1;
        if (check(mid)) {
            hi = mid;
        } else {
            lo = mid;
        }
    }
    cout << hi;
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    solve();    
    return 0;
}