\(i=1,2,\dots,N\) に対して、以下を行うアルゴリズムを考えます。

ここで、\(i<0\) または \(i>N\) に対する \(P_i\) は \(\infty\) とします。

• 変数として、$c=1,ans=\infty$ を持ち、以下を繰り返す。
• $ans$ を $ans,|P_i-P_{i-c}|+c$ の最小値に置き換える。
• $ans$ を $ans,|P_i-P_{i+c}|+c$ の最小値に置き換える。
• $c$ を $1$ 増やし、$c > ans$ であるか「$i-c < 0$ かつ $i+c >N$」であれば繰り返しを終える。
• $ans$ を出力する。

アルゴリズムの正当性は、繰り返しを終えたとき、それ以降では \(c > ans\) より、 \(|P_i-P_{i-c}| + c,|P_i-P_{i+c}|+c>ans\) であるため示されます。

計算量は、一見 \(c\) が各 \(i\) に対して \(\mathrm{O}(N)\) 回動くので \(\mathrm{O}(N^2)\) ですが、実は \(\mathrm{O}(N\sqrt N)\) で動作します。以下、それを示します。\(M=\lfloor \sqrt N \rfloor\)と置きます。

\(ans\) の更新を、\(\left\lfloor \frac{P_i}{M} \right\rfloor = \left\lfloor \frac{P_{i-c}}{M} \right\rfloor\) である場合についてのみ行うとします。(\(P_{i+c}\) についても同様)

このようにしても、計算量がよくなることはありません。

このとき、\(\left\lfloor \frac{P_i}{M} \right\rfloor\) が同じものに対して繰り返しの回数の総和を考えます。

\(1\) 度 \(ans\) を更新したら、それ以降の繰り返しの回数は \(\mathrm{O}(M)\) 回であり、\(ans\) を更新するまでの繰り返しの回数は総和を取ると \(\mathrm{O}(N)\) であるため、繰り返しの回数の総和は \(\mathrm{O}(N)\) となります。

\(\left\lfloor \frac{P_i}{M} \right\rfloor\) の種類は \(\mathrm{O}(M)\) 個であるため、全体での繰り返しの回数の総和は \(\mathrm{O}(NM)=\mathrm{O}(N\sqrt N)\) となります。

よって、上記のアルゴリズムの計算量は \(\mathrm{O}(N\sqrt N)\) となり、十分高速です。