0-basedで考える。列$(S_i)$を$[0, m), [m, N)$に分けた時に、左右の和を等しくするようなスワップが何個あるか数える。まず、右の和のほうが大きいことが有効なスワップが存在する必要条件である。右の和が左の和より$D(m)$だけ大きいとする。このとき、$D(m)$が偶数なら左の区間の$S_i$と右の区間の$S_{i+D(m)/2}$を交換すると和が等しくなる。添え字$i$が有効である条件は$0\le i < m, m \le i+ D(m)/2 < N$で、これは$\max(0, m-D(m)/2) \le i < \min(m, N-D(m)/2)$とまとまる。この区間の長さが有効なスワップの数に等しいので、すべての$m$について足せばよい。ただし$D(m)=0$の場合は区間をまたいで数を移動する必要がないので特別扱いして、左の区間内と右の区間内のスワップの総数を数える。
さて、$0\le D(m) < 2N$が必要なことを考えると、有効な$m$は多くないはずだ。$m$が増加するとき、$D(m)$が正から負に変わる地点を考えると、この地点は全体の半分よりは右にあるはずだから、その付近では$m$が$1$動くごとにおおむね$2 \cdot N/2 = N$程度は$D(m)$が変化することになる。したがって、高々3つ程度の$m$について数えれば十分という見積もりができる。実装の際は$D(m) \ge 0$であるような最大の$m$を二分探索などで求めておいて、そこから下っていけばよい。
