問題文

イタリアのチェゼナーティコ (Cesenatico) はアドリア海に面した港町であり，運河を持つことで知られている．運河には船が停泊しており，観光地としても知られている．ここで，現実を単純化した次のような状況設定を考えたい．

運河は直線状であり，その片側のみがアドリア海に通じている．また，運河には 1 から N までの番号が付けられた N 隻の船が停泊しており，船 i (1 \leqq i \leqq N) はアドリア海から距離 A_i 離れたところに停泊している．

ここで，番号が小さい船ほどアドリア海に近いところに停泊している．すなわち，A_1 < A_2 < \cdots < A_N が成立している．

あなたは町で行われる祭りのために船に色を塗ることにした．具体的にはそれぞれの船につき色 1 から色 N までの N 色の中から 1 色を選び，その色で船を塗る．ここで，以下の条件を満たしたい．

• どの色 c (1 \leqq c \leqq N) についても，色 c で塗られた船の数は 1 隻ではない．色 c で塗られた船が存在しなくてもよいことに注意せよ．
• 色 c で塗られた船が 2 隻以上ある場合，色 c で塗られた船は等間隔に並んでいる．言い換えると，色 c で塗られた船について，船のアドリア海からの距離を昇順に並べてできる列は等差数列である．

船の見栄えをより良くするために，以下で表される美しさを定義する．

• 同じ色で塗られた相異なる 2 隻の間の距離としてありうる最小値．ここで，船 i と船 j (1 \leqq i \leqq N，1 \leqq j \leqq N，i \neq j) の間の距離を | A_i - A_j | とする．

船の情報が与えられたとき，条件を満たす船の塗り方が存在するかを判定し，存在する場合は美しさとしてありうる最大値を求めるプログラムを作成せよ．

制約

• 2 \leqq N \leqq 3\,500．
• 1 \leqq A_i \leqq 10^9 (1 \leqq i \leqq N)．
• A_i < A_{i + 1} (1 \leqq i \leqq N - 1)．
• 入力される値はすべて整数である．

小課題

1. (8 点) A_i = i (1 \leqq i \leqq N)．
2. (11 点) N \leqq 7．
3. (12 点) N \leqq 100．
4. (39 点) N \leqq 700．
5. (30 点) 追加の制約はない．

入力例 1

2
1 2

出力例 1

1

例えば，条件を満たさない船の塗り方として以下のようなものが考えられる．

• 船 1 を色 1 で塗り，船 2 を色 2 で塗る．

この塗り方において，色 1 で塗られた船の数は 1 隻であるため条件を満たさない．

例えば，条件を満たす船の塗り方として以下のようなものが考えられる．

• 船 1 と船 2 を色 2 で塗る．

この塗り方において，色 1 で塗られた船は存在しないため，色 1 についての条件を満たす．また，色 2 で塗られた船のアドリア海からの距離を昇順に並べてできる列は (1, 2) であり，これは等差数列となるため，色 2 についての条件を満たす．したがって，この塗り方は条件を満たす．

この塗り方において，同じ色で塗られた 2 隻の組は船 1 と船 2 である．この 2 隻の間の距離は |A_1 - A_2| = |1 - 2| = 1 である．したがって，美しさは 1 である．

美しさを 2 以上にすることはできないため，1 を出力する．

この入力例はすべての小課題の制約を満たす．

入力例 2

3
1 10 100

出力例 2

-1

どの色についても，その色で塗られた船の数を 1 隻でないようにするには，船 1, 2, 3 を同じ色で塗る必要がある．

このとき，船 1 を塗った色で塗られた船のアドリア海からの距離を昇順に並べてできる列は (1, 10, 100) であり，これは等差数列でない．

したがって，条件を満たす船の塗り方が存在しないため，-1 を出力する．

この入力例は小課題 2, 3, 4, 5 の制約を満たす．

入力例 3

5
5 6 8 9 11

出力例 3

3

例えば，条件を満たす船の塗り方として以下のようなものが考えられる．

• 船 1 と船 3 と船 5 を色 1 で塗り，船 2 と船 4 を色 4 で塗る．

この塗り方において，同じ色で塗られた 2 隻の組は船 1 と船 3，船 1 と船 5，船 2 と船 4，船 3 と船 5 の 4 組である．これらの組における 2 隻の間の距離はそれぞれ 3, 6, 3, 3 である．したがって，美しさは 3 である．

美しさを 4 以上にすることはできないため，3 を出力する．

この入力例は小課題 2, 3, 4, 5 の制約を満たす．