Sample 1 - Pasta Normalization Problem

2 secs 1024 MB
uni_kakurenbo

この問題はサンプルです

注意


Sample 0 の注意事項を先にお読みください。

問題文


個の小パスタが繋がってできた大パスタがあります.
左から 番目の小パスタの長さは です.

この大パスタを何回か折って,いくつかの中パスタ (小パスタがいくつか繋がったもの) に再び分割しようとしています.
ただし,見栄えのために,すべての中パスタの長さが等しくなるようにする必要があります.
このとき最大でいくつの中パスタへ分割することができますか?
求めてください.

大パスタは,それを構成する小パスタ同士の繋ぎ目でのみ折ることができます.

制約


入力


各テストケースの入力は,それぞれ以下の形式で与えられる:


出力


答えを出力せよ.

サンプル


入力例1
2
8
1 2 3 2 4 4 2 6
5
1 2 3 4 5
出力例1
4
1
  1. であるので,長さ の中パスタ つに分割することができます.(他に,たとえば長さ の中パスタ つに分割することもできますが, が最大です.)
  2. 長さが の中パスタ つに分割することができます.

提出


Go (1.14)