AtCoder Regular Contest 152 C
（工事中）
問題
操作を何度行っても、数列内の2項間の差の絶対値は常に等しく、操作を行う度に符号が反転するだけであるため、数列の最大値と最小値の差は常に$ d = a_{1}-a_{N} で一定である。よって、数列の最大値を小さくすることと、数列の最小値を小さくすることは同義であるため、数列の最小値として取りうる値の最小値を求めれば良い。
ここで、下の$ N-1 個の正整数の最大公約数を$ g とする。（問題の仮定より$ 0 は下に含まれない）
$ 2(a_{i+1} - a_{i}) $ (i = 1,2,\ldots,N-1)
結論を先に述べると、求めるべき値（数列の最小値として取りうる値の最小値）は、下の$ N+1 個の数のうち、最小のものである。
$ a_{1} を$ g で割ったときの余り
$ 2a_{i} - a_{N} を$ g で割った余り $ (i = 1,2,\ldots,N)
※ 実は$ a_{1} を$ g で割ったときの余りと$ a_{N} を$ g で割ったときの余りだけを考えれば十分である（詳細は解説との違いの考察に記載する）
これは、最大公約数の計算をにユークリッドの互除法を使用すれば、$ O(N \log a_{N}) の計算量で計算できる。
よって、以降は上の事実を証明する。
ここで、$ 1 以上$ N 以下の整数からなる長さが有限の数列$ \bm{\sigma} を「操作列」とよび、$ \mathbf{Opr} を操作列全体の集合とする。
また、操作列$ \bm{\sigma} の長さを$ |\bm{\sigma}| と表し、正整数$ i について操作列$ \bm{\sigma} の$ i 番目の値を（存在するときは）$ \sigma_{i} で表す。
※ 操作列に関する定義や記法などは、証明の都合で導入したものであり、この記事内でのみ使われるものである。
例えば、$ \bm{\sigma} = (5,4,3,2,1) という操作列があった場合、$ |\bm{\sigma}| = 5 であり、$ \sigma_{4} = 2 である。
ここで操作列$ \bm{\sigma} と、$ 1 以上$ N 以下の整数$ i について、$ a^{\bm{\sigma}}_{i} = (-1)^{|\bm{\sigma|}} a_{i} + \sum_{j = 1}^{|\bm{\sigma}|} (-1)^{j+1}\times2a_{\sigma_{j}} とする。
すなわち、下のように$ a^{\bm{\sigma}}_{i} を定義する。
$ |\bm{\sigma}| が奇数のときは、$ a^{\bm{\sigma}}_{i} = 2a_{\sigma_{1}}-2a_{\sigma_{2}}+\cdots+2a_{\sigma_{|\bm{\sigma}|}} - a_{i}
$ |\bm{\sigma}| が偶数のときは、$ a^{\bm{\sigma}}_{i} = 2a_{\sigma_{1}}-2a_{\sigma_{2}}+\cdots+2a_{\sigma_{|\bm{\sigma}|-1}}-2a_{\sigma_{|\bm{\sigma}|}} + a_{i}
操作列$ \bm{\sigma} に従って操作した後、すなわち$ 1 \le i \le |\bm{\sigma}| を満たす整数$ i それぞれについて$ i 回目のときに$ \sigma_{i} 番目の項を選ぶ操作を行った後に、（もしその操作が許されたものであるなら）数列の$ i 番目の項の値が$ a^{\bm{\sigma}}_{i} となることは帰納法から確認できる。
つまり、操作列$ \bm{\sigma} を動かしたときに、$ a^{\bm{\sigma}}_{i} が取り得る値を考えれば良さそうではあるが、$ \mathbf{Opr} には許可されていない操作列も含まれる。
よって、操作列$ \bm{\sigma} が次の条件を満たすとき、この操作列は「許可されている」とし、許可されている操作列全体の集合$ \mathbf{POpr} を考える。
操作列$ \bm{\sigma} の任意のプレフィックス$ \bm{\sigma}^{\prime} および$ 1 \le i \le N を満たす任意の整数$ i について$ a_{i}^{\bm{\sigma}} \ge 0
これは、問題文に書かれている、操作が可能な条件そのものである。よって、求めたい値は$ \min_{\bm{\sigma} \in \mathbf{POpr}} \min_{1 \le i \le N} a_{i}^{\bm{\sigma}} である。
さて、本来であれば許可されている操作列のみを考える必要があるが、実は下の事実が成り立つ。
そのため、操作後の最終的な数列の最小値が非負である場合は許可された操作列か否かを気にする必要はなくなる。
任意の非負整数$ k について、$ \exists \bm{\sigma} \in \mathbf{Opr}. \min_{1 \le i \le N} a_{i}^{\bm{\sigma}} = k \iff \exists \bm{\sigma} \in \mathbf{POpr}. \min_{1 \le i \le N} a_{i}^{\bm{\sigma}} = k
右から左については、定義から$ \mathbf{Opr} \subseteq \mathbf{POpr} であるため、明らかに成り立つ。よって、左を仮定して右を示す。
操作列$ \bm{\sigma} が、$ \min_{1 \le i \le N} a_{i}^{\bm{\sigma}} = k を満たすと仮定する。このとき、操作列$ \bm{\sigma} から、許可された操作列$ \bm{\sigma}^{\prime} を実際に構築する。
具体的には、操作列$ \bm{\sigma} の各要素$ \sigma_{i} を、$ i が奇数のときは$ (N, 1, \sigma_{i}) に、$ i が偶数のときは$ (1, N, \sigma_{i}) に置き換えた後に、
追加した$ N や$ 1 を打ち消すように、同じ数だけ$ N や$ 1 を追加して、長さが$ 5|\bm{\sigma}| の操作列$ \bm{\sigma}^{\prime} を作る。
※ あくまでこれは証明のために考えた一例であり、操作列$ \bm{\sigma} から許可された操作列$ \bm{\sigma}^{\prime} を構築する方法は、他にも考えられる。
この操作列$ \bm{\sigma}^{\prime} について、より厳密に書き下すと下のようになる。
$ i が$ 1 \le i \le 3N かつ$ i \equiv 1,5 \mod 6 を満たす整数のとき、$ \sigma^{\prime}_{i} = N
$ i が$ 1 \le i \le 3N かつ$ i \equiv 2,4 \mod 6 を満たす整数のとき、$ \sigma^{\prime}_{i} = 1
$ i が$ 1 \le i \le 3N かつ$ i \equiv 0 \mod 3 を満たす整数のとき、$ \sigma^{\prime}_{i} = \sigma_{i/3}
$ i が$ 3N \lt i \le 5N かつ$ i \equiv 0 \mod 2 を満たす整数のとき、$ \sigma^{\prime}_{i} = N
$ i が$ 3N \lt i \le 5N かつ$ i \equiv 1 \mod 2 を満たす整数のとき、$ \sigma^{\prime}_{i} = 1
この操作列$ \bm{\sigma}^{\prime} は、操作列$ \bm{\sigma} に$ 1 や$ N を追加し、最後にそれを打ち消す形で$ 1 や$ N を追加しているので、$ a_{i}^{\bm{\sigma^{\prime}}} = a_{i}^{\bm{\sigma}} を満たす。
よって、この$ \bm{\sigma}^{\prime} が許可された操作列であることがわかれば、上の事実が証明されたことになる。
この$ \bm{\sigma}^{\prime} が許可された操作列であることは、厳密には帰納法により証明することもできると思われるが、ここでは概要だけ述べる。
まず$ i が$ 1 \le i \le 3N かつ$ i \not\equiv 0 \mod 3 のときは、その操作の直前の数列において最大値となる項を選んで操作をしている。
最大値となる項を選んで操作をすると、操作後の数列の全ての項は操作する直前の数列の最大値以上の値となっている。
また、帰納法の仮定より、操作する直前の数列の最小値は非負であることと、最小値と最大値の差が常に$ d であることから、
操作直前の数列の最大値は$ d 以上である。よって、最大値となる項を選んだ操作を行った場合は、全ての項の値が$ d 以上となる。
そして、数列の全ての項が$ d 以上であるときは、どの項を選んでも操作が可能である。
選んだ項は必ず$ d 以上であり、最大値と選んだ項との差は$ d 以下であることから、選んだ項の2倍は必ず最大値以上になる。
よって、操作列$ \bm{\sigma}^{\prime} の$ 3N 番目までの操作については許可されたものであることがわかる。
最後に、それより後ろの操作についてだが、ここでは常に数列の各項の値が減る操作を行っている。
数列の各項の値が狭義単調減少していき、さらに仮定より最終的な値は非負整数$ k 以上であるため、常に非負であることがわかる。
よって、これで操作列$ \bm{\sigma}^{\prime} の全ての操作が許可されていることが確認できたため、上の事実が証明できた。
さて、以上から操作列$ \bm{\sigma} が許可された操作列かどうかは意識する必要がないことがわかったため、$ \{ \min_{1 \le i \le N} a_{i}^{\bm{\sigma}} \mid \bm{\sigma} \in \mathbf{Opr} \} を考える。
ここで
$ |\bm{\sigma}| が奇数である任意の操作列$ \bm{\sigma} と、$ 1 \le i \le N を満たす任意の整数$ i および任意の整数$ k について以下が
$ \exists \bm{\sigma} \in \mathbf{Opr}. a_{i}^{\bm{\sigma}} = k \iff \exists \bm{k}^{\bm{\sigma}}=(k^{\bm{\sigma}}_{1},k^{\bm{\sigma}}_{2},\ldots,k^{\bm{\sigma}}_{N-1}) \in \mathbb{Z}. \exists j \in \{ 1, 2, \ldots, N \}.\left(\right)