提供一种考场上想到的线段树乱搞解法。

一个环上有 $n$ 个点，第 $i$ 个点权值为 $a_i$，当你来到一个点，就能取得这个点的权值。问：在最多绕一圈（经过 $n$ 个点）的情况下所能取到的最多的权值。

先考虑暴力做法：

先断环为链，并维护一个前缀和数组 $sum$，枚举两个点 $i,j$，保证 $1 \le i < j \le 2n$，找出 $sum_j-sum_i$ 的最大值即可。时间复杂度 $O(n^2)$。

这样显然会超时。考虑优化：

不难看出，在 $sum_i$ 一定时，$sum_j$ 越大，结果就越大，也就越有可能冲击最优解。又因为 $i < j \le 2n$，所以 $sum_j-sum_i$ 的最大值就是 $\max_{i < j \le 2n} sum_j -sum_i$。于是问题就变成了寻找区间最大值，可以用线段树在 $O(\log n)$ 的时间内解出。这样，总的时间复杂度就变成了 $O(n \log n)$，可以通过。

最后还有一点：不要忘记开 long long！