A国とB国という2つの国が戦争をしている。A国の軍人であるあなたはn人の兵士を率いて、B国の領土を占領する事になった。
B国の領土は2次元グリッドで表されている。あなたが最初に占領する場所は二次元グリッド上のある1マスである。 あなたが率いている兵士たちは、それぞれhiの体力を持っている。 それぞれの兵士は体力を1を消費して移動することができる。 現在いるマスを(a,b)とすると、(a+1,b),(a-1,b),(a,b+1),(a,b-1)の4方向を移動先として選ぶことが可能である。 兵士は体力が0になったらそこから動くことができなくなる。 一人以上の兵士が通過したマスはすべて占領することができる。
あなたの仕事は、最大でいくつのマスを占領することができるかを求めることである。
ただし、この2次元グリッドのサイズは無限に広いとすること。
入力は以下のフォーマットで与えられる。
n h1 . . . hn
入力は以下の制約を満たす
1 ≤ n ≤ 500
1 ≤ hi ≤ 10,000,000
答えの値を1行に出力せよ
2 5 5
11
10 10 10 10 10 10 10 10 10 10 10
93
5 1 2 3 4 5
15