ユニークビジョンプログラミングコンテスト2022 夏 (AtCoder Beginner Contest 268) E - Chinese Restaurant (Three-Star Version) (500)
長さ$ 2nで一直線になっていると考えると、ある区間$ \frac{n}{2}位はプラスとしてその後の$ \frac{n}{2}位はマイナスとして扱うことができる
位というのは$ nの偶奇によって変わる
区間の和は$ \mathcal{O}(\log N)で求まるので各回転毎に計算しても$ \mathcal{O}(N \log N)