Пікнік#499

Пікнік

1 saniyə
256 meqabayt
Medium

Василько має пиріг, розрізаний на шматочків. Вага кожного шматочка становить a_1, a_2, \dots, a_n. Він хоче поділити всі шматочки між собою та друзями так, щоб кожен отримав порцію однакової ваги.

Пиріг потрібно ділити за такими правилами:

Допоможіть Васильку порахувати, яку максимальну кількість друзів він може запросити на пікнік.

Input

Перший рядок містить одне число (1 \le n \le 5000) — кількість кусочків пирога.

Другий рядок містить цілих чисел a_{1}, a_2, \dots, a_{n} (1 \le a_{i} \le 10^4) — вага кожного кусочка пирога.

Output

Одне ціле число, максимальну кількість друзів, котрих може запросити Василько.

Examples

Example 1

Loading
Loading

Example 2

Loading
Loading

Note

У першому прикладі він може розділити пиріг на частин, де вага кожної частини буде . Це можна зробити, наприклад, так: 1+3, , 2+2, 3+1, , 1+1+2. Оскільки буде всього частин, то він може запросити лише друзів.

У другому прикладі він може лише розділити пиріг на частину (весь пиріг). У такому випадку він не може запросити друзів.