思路与算法

先考虑除全局最小值以外的起点。全局最小值必在最后被拿走；把它取掉后旋转成线性序列，两端的外部边界均是这个最小值。单调栈建立最小笛卡尔树。起点u所在子树的所有数都比两侧祖先边界大，因此该子树会先被消费，外展过程是把左侧逆序和右侧正序按当前较大前沿合并。记录整个删除序列的交错和D=第1项-第2项+第3项-…，则先手分数=(全部总和+D)/2。预处理原序列的交错前缀和，连续区间无论正序或逆序都可O(1)求交错和。求u子树内部交错和时，逐个扫描较短一侧；在线段树上寻找较长一侧第一个比当前短侧前沿更小的位置，将此前连续大段一次加入，再加入短侧前沿。所有结点的较短侧总长度O(n log n)。子树消费完后，从父亲到另一侧子树的序列是一个连续的正序或逆序区间，按长度奇偶沿父子关系计算外部交错和。合并内外即可回答全部非最小值起点。最小值作为第一步时例外，直接进行一次圆周双端模拟O(n)。

正确性说明

最小值从不优于另一个候选，故除首步选它外必最后删除。最小笛卡尔树子树是连续区间，区间内所有值大于其两侧外界祖先；从区间内起步，边界外的数无法抢在区间内候选之前被选，因此先完整消费自身子树。区间内左右暴露的候选顺序固定为左逆序、右正序，线段树跳过的长侧连续段都严格大于短侧当前值，逐段合并与题定逐步比较完全一致。子树消费后必须先取父亲，再沿另一侧子树靠近端依次消耗，直至转入更外层；外部递推因此精确。交错和拼接规律是D(XY)=D(X)+(-1)^|X|D(Y)，用于各段、各层和内外合并，故所得D就是真实删除序列交错和。全部总和与交错和相加恰为先手所得的两倍。最小值首步另以原规则直接模拟，所以覆盖全部起点。

复杂度

令D为输入数及中间和的最大十进制位数。单调栈建树、遍历和交错前缀初始化O(nD)，线段树初始化O(nD)。每个结点扫描较短孩子区间，按small-to-large计费总扫描O(n log n)，每次找阈值边界O(log n)次比较，所以总O(n log²n·D)，空间O(nD)。当所有数的绝对值不超过10^12时用int64分支，n<=300000保证加减安全，数值运算视为O(1)；否则启用内联精确大整数。全局最小值首步的单次模拟另O(nD)。

易错点

Ai仅规定上界，不能假设非负；大负数必须精确运算。N=1直接输出本数。每次取数规则完全确定，不能改成两人博弈取最优。连续段逆序时交错和的首项符号由右端下标决定。外部串长度和子树大小的奇偶必须分别处理。总和+D为偶数，即便结果为负也无需浮点除法。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
struct cpp_int {
    string s;
    bool neg;
    cpp_int(long long v = 0) : s(to_string(v)), neg(v < 0) {
        if (neg)
            s.erase(s.begin());
    }
    void norm() {
        auto p = s.find_first_not_of('0');
        s = p == string::npos ? "0" : s.substr(p);
        if (s == "0")
            neg = false;
    }
    static int cmpabs(const cpp_int &a, const cpp_int &b) {
        if (a.s.size() != b.s.size())
            return a.s.size() < b.s.size() ? -1 : 1;
        return a.s == b.s ? 0 : a.s < b.s ? -1 : 1;
    }
    friend bool operator<(const cpp_int &a, const cpp_int &b) {
        if (a.neg != b.neg)
            return a.neg;
        int c = cmpabs(a, b);
        return a.neg ? c > 0 : c < 0;
    }
    friend bool operator==(const cpp_int &a, const cpp_int &b) {
        return a.neg == b.neg && a.s == b.s;
    }
    friend bool operator!=(const cpp_int &a, const cpp_int &b) {
        return !(a == b);
    }
    friend bool operator>(const cpp_int &a, const cpp_int &b) {
        return b < a;
    }
    friend bool operator<=(const cpp_int &a, const cpp_int &b) {
        return !(b < a);
    }
    friend bool operator>=(const cpp_int &a, const cpp_int &b) {
        return !(a < b);
    }
    cpp_int operator-() const {
        cpp_int r = *this;
        if (r.s != "0")
            r.neg = !r.neg;
        return r;
    }
    friend cpp_int operator+(const cpp_int &a, const cpp_int &b) {
        cpp_int r;
        r.s.clear();
        int carry = 0;
        if (a.neg == b.neg) {
            int i = (int)a.s.size() - 1, j = (int)b.s.size() - 1;
            while (i >= 0 || j >= 0 || carry) {
                int v = carry + (i >= 0 ? a.s[i--] - '0' : 0) + (j >= 0 ? b.s[j--] - '0' : 0);
                r.s += char('0' + v % 10);
                carry = v / 10;
            }
            r.neg = a.neg;
        } else {
            const cpp_int *x = &a, *y = &b;
            if (cmpabs(a, b) < 0)
                swap(x, y);
            int i = (int)x->s.size() - 1, j = (int)y->s.size() - 1;
            while (i >= 0) {
                int v = x->s[i--] - '0' - carry - (j >= 0 ? y->s[j--] - '0' : 0);
                carry = v < 0;
                if (carry)
                    v += 10;
                r.s += char('0' + v);
            }
            r.neg = x->neg;
        }
        reverse(r.s.begin(), r.s.end());
        r.norm();
        return r;
    }
    friend cpp_int operator-(const cpp_int &a, const cpp_int &b) {
        return a + (-b);
    }
    friend cpp_int operator*(const cpp_int &a, int b) {
        cpp_int r;
        r.s.clear();
        long long carry = 0;
        long long z = b;
        if (z < 0)
            z = -z;
        for (int i = (int)a.s.size() - 1; i >= 0; i--) {
            carry += (a.s[i] - '0') * z;
            r.s += char('0' + carry % 10);
            carry /= 10;
        }
        while (carry) {
            r.s += char('0' + carry % 10);
            carry /= 10;
        }
        reverse(r.s.begin(), r.s.end());
        r.neg = a.neg ^ (b < 0);
        r.norm();
        return r;
    }
    friend cpp_int operator/(const cpp_int &a, int b) {
        cpp_int r;
        r.s.clear();
        long long rem = 0, z = b;
        if (z < 0)
            z = -z;
        for (char c : a.s) {
            rem = rem * 10 + c - '0';
            r.s += char('0' + rem / z);
            rem %= z;
        }
        r.neg = a.neg ^ (b < 0);
        r.norm();
        return r;
    }
    cpp_int &operator+=(const cpp_int &b) {
        *this = *this + b;
        return *this;
    }
    cpp_int &operator-=(const cpp_int &b) {
        *this = *this - b;
        return *this;
    }
    cpp_int &operator*=(int b) {
        *this = *this * b;
        return *this;
    }
    friend istream &operator>>(istream &in, cpp_int &a) {
        string v;
        if (in >> v) {
            a.neg = v[0] == '-';
            if (v[0] == '-' || v[0] == '+')
                v.erase(v.begin());
            a.s = v;
            a.norm();
        }
        return in;
    }
    friend ostream &operator<<(ostream &out, const cpp_int &a) {
        if (a.neg)
            out << '-';
        return out << a.s;
    }
};

// The range-minimum tree finds the first/last value smaller than a threshold.
template <class I> struct Solver {
    int n, k, root, p;
    vector<I> a, pref, inside, ext;
    vector<int> l, r, par, lo, hi, sz, mn;
    vector<I> orig;
    Solver(vector<I> v) : n(v.size()), orig(v) {
    }
    I alt(int x, int y, bool reverse = false) {
        if (x > y)
            return I(0);
        I z = pref[y + 1] - pref[x];
        return ((reverse ? y : x) & 1) ? -z : z;
    }
    int findbelow(int z, int L, int R, int ql, int qr, const I &v, bool rev) {
        if (R < ql || qr < L || mn[z] < 0 || !(a[mn[z]] < v))
            return -1;
        if (L == R)
            return L;
        int M = (L + R) / 2, first = rev ? z * 2 + 1 : z * 2, second = rev ? z * 2 : z * 2 + 1;
        int t = rev ? findbelow(first, M + 1, R, ql, qr, v, rev)
                    : findbelow(first, L, M, ql, qr, v, rev);
        if (t >= 0)
            return t;
        return rev ? findbelow(second, L, M, ql, qr, v, rev)
                   : findbelow(second, M + 1, R, ql, qr, v, rev);
    }
    I mergealt(int u) {
        int L = lo[u], R = hi[u], nl = u - L, nr = R - u;
        if (!nl)
            return a[u] - alt(u + 1, R);
        if (!nr)
            return a[u] - alt(L, u - 1, true);
        bool smallleft = nl < nr;
        int s = smallleft ? u - 1 : u + 1, se = smallleft ? L : R, sd = smallleft ? -1 : 1;
        int b = smallleft ? u + 1 : u - 1, be = smallleft ? R : L, bd = smallleft ? 1 : -1;
        I ans = a[u];
        int parity = 1;
        auto add = [&](I z, int len) {
            if (parity)
                ans -= z;
            else
                ans += z;
            parity ^= (len & 1);
        };
        while ((sd > 0 ? s <= se : s >= se) && (bd > 0 ? b <= be : b >= be)) {
            int ql = min(b, be), qr = max(b, be);
            int t = findbelow(1, 0, k - 1, ql, qr, a[s], bd < 0);
            if (t < 0) {
                add(alt(ql, qr, bd < 0), abs(be - b) + 1);
                b = be + bd;
                break;
            }
            if (t != b) {
                int e = t - bd;
                add(alt(min(b, e), max(b, e), bd < 0), abs(e - b) + 1);
                b = t;
            }
            add(a[s], 1);
            s += sd;
        }
        if (sd > 0 ? s <= se : s >= se)
            add(alt(min(s, se), max(s, se), sd < 0), abs(se - s) + 1);
        if (bd > 0 ? b <= be : b >= be)
            add(alt(min(b, be), max(b, be), bd < 0), abs(be - b) + 1);
        return ans;
    }
    void run() {
        if (n == 1) {
            cout << orig[0] << '\n';
            return;
        }
        p = min_element(orig.begin(), orig.end()) - orig.begin();
        for (int j = 1; j < n; j++)
            a.push_back(orig[(p + j) % n]);
        int N = n - 1;
        l.assign(N, -1);
        r = l;
        par = l;
        vector<int> st;
        for (int i = 0; i < N; i++) {
            int last = -1;
            while (!st.empty() && a[i] < a[st.back()]) {
                last = st.back();
                st.pop_back();
            }
            if (!st.empty()) {
                r[st.back()] = i;
                par[i] = st.back();
            }
            if (last >= 0) {
                l[i] = last;
                par[last] = i;
            }
            st.push_back(i);
        }
        root = st[0];
        vector<int> order(1, root);
        for (size_t j = 0; j < order.size(); j++) {
            int u = order[j];
            if (l[u] >= 0)
                order.push_back(l[u]);
            if (r[u] >= 0)
                order.push_back(r[u]);
        }
        lo.resize(N);
        hi.resize(N);
        sz.resize(N);
        inside.resize(N);
        ext.resize(N);
        pref.assign(N + 1, I(0));
        for (int i = 0; i < N; i++)
            pref[i + 1] = pref[i] + (i & 1 ? -a[i] : a[i]);
        k = 1;
        while (k < N)
            k *= 2;
        mn.assign(k * 2, -1);
        for (int i = 0; i < N; i++)
            mn[k + i] = i;
        for (int j = k - 1; j; j--) {
            int x = mn[j * 2], y = mn[j * 2 + 1];
            mn[j] = x < 0 ? y : y < 0 ? x : a[x] < a[y] ? x : y;
        }
        for (int j = N - 1; j >= 0; j--) {
            int u = order[j];
            lo[u] = l[u] < 0 ? u : lo[l[u]];
            hi[u] = r[u] < 0 ? u : hi[r[u]];
            sz[u] = hi[u] - lo[u] + 1;
            inside[u] = mergealt(u);
        }
        ext[root] = orig[p];
        for (int u : order) {
            if (l[u] >= 0) {
                I z = a[u] - alt(u + 1, hi[u]);
                int len = 1 + hi[u] - u;
                ext[l[u]] = z + (len & 1 ? -ext[u] : ext[u]);
            }
            if (r[u] >= 0) {
                I z = a[u] - alt(lo[u], u - 1, true);
                int len = 1 + u - lo[u];
                ext[r[u]] = z + (len & 1 ? -ext[u] : ext[u]);
            }
        }
        I total = 0;
        for (I x : orig)
            total += x;
        vector<I> ans(n);
        for (int i = 0; i < N; i++) {
            I diff = inside[i] + (sz[i] & 1 ? -ext[i] : ext[i]);
            ans[(p + i + 1) % n] = (total + diff) / 2;
        }
        I d = orig[p];
        int L = 0, R = N - 1, turn = 1;
        while (L <= R) {
            I x;
            if (a[R] < a[L])
                x = a[L++];
            else
                x = a[R--];
            if (turn)
                d -= x;
            else
                d += x;
            turn ^= 1;
        }
        ans[p] = (total + d) / 2;
        for (I x : ans)
            cout << x << '\n';
    }
};
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<string> s(n);
    bool small = true;
    for (string &x : s) {
        cin >> x;
        string z = x;
        if (z[0] == '-' || z[0] == '+')
            z.erase(z.begin());
        size_t f = z.find_first_not_of('0');
        z = f == string::npos ? "0" : z.substr(f);
        if (z.size() > 12)
            small = false;
    }
    if (small) {
        vector<long long> v;
        for (auto x : s)
            v.push_back(stoll(x));
        Solver<long long>(v).run();
    } else {
        vector<cpp_int> v(n);
        for (int i = 0; i < n; i++) {
            istringstream in(s[i]);
            in >> v[i];
        }
        Solver<cpp_int>(v).run();
    }
}