問題文

バーチャルYoutuberの卯月ロウは、コーヒー豆が大好きでした。 どれくらい好きかというと自分で豆を煎ってしまうほどです。 この世界のコーヒー豆には正の整数で表される「美味しさ度」というものがそれぞれに存在し、各豆がどれくらい美味しいかを表しています。

卯月ロウは、このコーヒー豆を合計$N$個持っており、これらは数列$a$で表されます。 左から$i$番目のコーヒー豆の美味しさ度は$a_i$で表されます。

卯月ロウは、数列$a$に含まれるコーヒー豆の美味しさ度がバラバラだと苦味が多く含まれてしまうため、 すべてのコーヒー豆の美味しさ度が等しくなるよう好きな回数だけ自由に操作を行うことにしました。

行える操作は以下のようなのものです。

• 今の数列$a$の要素数を$K$とする。このとき、左から$i(1{\leq}i{\leq}K-1)$番目のコーヒー豆と$i+1$番目の隣り合う$2$つのコーヒー豆を煎って $1$つにする。このとき、新しくできるコーヒー豆の美味しさ度は$a_i+a_{i+1}$となる。 ただし、$K>1$のときのみ行えることに注意する(隣り合うコーヒー豆が必要であるため)。

卯月ロウは、以上の操作を繰り返しすべてのコーヒー豆の美味しさ度を等しくしながら、できるだけ操作終了時に残っているコーヒー豆の数$R$を最大にしたいです。 操作終了時に残っている最大のコーヒー豆の数$R$を求めてください。

入力

$N$
$a_1 \ a_2 \ ...\ a_N$

• 入力はすべて整数
• $1{\leq}N{\leq}10^5$
• $1{\leq}a_i{\leq}10^2$

出力

最後に改行してください。

サンプル

8
5 2 2 3 1 1 4 3

3

1
50

1

60
36 45 67 64 100 2 3 22 52 64 9 22 53 63 45 60 56 26 68 33 87 23 91 81 71 34 37 91 51 26 44 76 93 1 34 100 3 22 53 23 61 8 85 90 49 6 40 45 66 80 36 32 21 88 40 42 78 97 99 6 

3