N 個のセグメントに分かれている 1 次元のケーキがあり、i (1 ≦ i ≦ N) 番目のセグメントには A_i 個のイチゴが載っています。

切れ目を 2 つ選んで 3 つのケーキにわけたとき、3 つのケーキに乗っているイチゴの数のうち、最大値と最小値の差の最小値を求めてください。

(制約) 3 ≦ N ≦ 200000, 1 ≦ A_i ≦ 10 ^ 9 (1 ≦ i ≦ N)


この問題を解いてみましょう。1 つ目の切れ目を全探索して解いてみることを考えます。

1 つ目の切れ目を固定すると、左側のケーキのイチゴの数は確定します。なので、真ん中のケーキと右側のケーキのイチゴの数に注目していきます。イチゴの数の総和を S とします。

左側のイチゴの数(定数)を l 、右側のイチゴの数(変数)を r とすると、真ん中のイチゴの数は、S - l - r となります。

l と r と S - l - r の大小関係についてそれぞれのパターンで考えていきます。

(1) l が最も小さいとき

そのとき max(r, S - l - r) を出来るだけ小さくするのが最適になります。よって、最も左にある左得切れ目か、最も右にある右得切れ目のどちらかで切ることが最適になります。(そうでない場合、左得切れ目で切った場合は S - l - r が大きくなり、右得切れ目で切った場合には r が大きくなってしまいます。)

(2) l が最も大きいとき

そのとき min(r, S - l - r) を出来るだけ大きくするのが最適になります。よって、最も左にある左得切れ目か、最も右にある右得切れ目のどちらかで切ることが最適になります。

(3) それ以外のとき

問題 3 と同じ設定になります。よって、最も左にある左得切れ目か、最も右にある右得切れ目のどちらかで切ることが最適になります。

よって、r の変化において、l と r と S - l - r の大小関係は変化しますが、どの場合であっても、最も左にある左得切れ目か、最も右にある右得切れ目のどちらかで切ることが最適になります。

このことを踏まえて問題を解いてみましょう。

(問題)

N 個のセグメントに分かれている 1 次元のケーキがあり、i (1 ≦ i ≦ N) 番目のセグメントには A_i 個のイチゴが載っています。

切れ目を 2 つ選んで 3 つのケーキにわけたとき、3 つのケーキに乗っているイチゴの数のうち、最大値と最小値の差の最小値を求めてください。