Link
不妨记 \(A = a_1,a_2,\dots,a_n\) 和 \(B = a_{n+1},a_{n+2},\dots,a_{2n}\)
考虑“交换”对 \(A\) 和 \(B\) 的影响，会发现它们都变成了环形，如图。
所以答案首先可能产生自环形的 \(A\) 和 \(B\)，分别计算一下。之后，答案还可能会产生自 \(A\) 和 \(B\) 相接的部分，如图。
会发现其实是环形 \(B\) 的一个最大后缀，加上环形 \(A\) 的一个最大前缀。之后还要 reverse 一下，重新做一遍，因为相接的地方有两处。