레이팅 미적용イタリアのチェゼナーティコ (Cesenatico) はアドリア海に面した港町であり,運河を持つことで知られている.運河には船が停泊しており,観光地としても知られている.ここで,現実を単純化した次のような状況設定を考えたい.
運河は直線状であり,その片側のみがアドリア海に通じている.また,運河には 1 から N までの番号が付けられた N 隻の船が停泊しており,船 i ( \(1 \le i \le N\) ) はアドリア海から距離 A i 離れたところに停泊している.
ここで,番号が小さい船ほどアドリア海に近いところに停泊している.すなわち, A 1 < A 2 < ... < A N が成立している.
あなたは町で行われる祭りのために船に色を塗ることにした.具体的にはそれぞれの船につき色 1 から色 N までの N 色の中から 1 色を選び,その色で船を塗る.ここで,以下の条件を満たしたい.
どの色 c ( \(1 \le c \le N\) ) についても,色 c で塗られた船の数は 1 隻 ではない .色 c で塗られた船が 存在しなくてもよい ことに注意せよ.
色 c で塗られた船が 2 隻以上ある場合,色 c で塗られた船は等間隔に並んでいる.言い換えると,色 c で塗られた船について,船のアドリア海からの距離を昇順に並べてできる列は等差数列である.
船の見栄えをより良くするために,以下で表される 美しさ を定義する.
同じ色で塗られた相異なる 2 隻の間の距離としてありうる最小値.ここで,船 i と船 j ( \(1 \le i \le N\) , \(1 \le j \le N\) , \(i \ne j\) ) の間の距離を |A i − A j | とする.
船の情報が与えられたとき,条件を満たす船の塗り方が存在するかを判定し,存在する場合は美しさとしてありうる最大値を求めるプログラムを作成せよ.
2 ≦ N ≦ 3 500 .
1 ≦ A i ≦ 10 9 ( \(1 \le i \le N\) ).
A i < A i+1 ( 1 ≦ i ≦ N − 1 ).
入力される値はすべて整数である.
( 8 点) A i = i ( \(1 \le i \le N\) ).
( 11 点) \(N \le 7\) .
( 12 点) \(N \le 100\) .
( 39 点) \(N \le 700\) .
( 30 点) 追加の制約はない.
入力は以下の形式で与えられる.
N
A 1 A 2 A 3 ... A N
条件を満たす船の塗り方が存在しない場合は -1 を出力せよ.存在する場合は美しさとしてありうる最大値を 1 行で出力せよ.
2
1 2
1
3
1 10 100
-1
5
5 6 8 9 11
3