传送门

考虑二分答案 \(sum\)，判断是否可行。

记前缀和为 \(s\)，这里令编号为 \(1...2n\)。

则每个要求可以转化为 \(s_{i + n - 1} - s_{i - 1} \ge a_i\) 或者 \(s_{i - 1} - s_{i - n - 1} \le sum - a_i\)。

这样巧妙的将环变成了序列。

容易发现，只用 \(s_i, s_{i + n}\) 会相互制约，并且 \(s_i \le s_{i + 1}\)。

考虑枚举 \(s_n\) 的值，按照 \(i = 0...n - 1\) 贪心处理每一对 \(s_{i}, s_{i + n}\)。

每次尽量在 \(a_{i + 1}\le s_{i + n} - s_{i} \le sum - a_{i + n + 1}\) 的前提下，使 \(s_{i},s_{i + n}\) 小。

不合法时调整即可，最后判断 \(s_{n - 1} \le s_n:(1), s_{2n - 1} \le sum:(2)\) 即可。

分析可得 \((1),(2)\) 关于 \(s_n\) 的大小是否成立是单调的，只需找出最小的满足 \((1)\) 的 \(s_n\) 验证 \((2)\) 即可。

所以二分套二分，复杂度 \(O(n\log^2a)\)。

代码