Василько має пиріг, розрізаний на шматочків. Вага кожного шматочка становить a_1, a_2, \dots, a_n. Він хоче поділити всі шматочки між собою та друзями так, щоб кожен отримав порцію однакової ваги.
Пиріг потрібно ділити за такими правилами:
Кожна людина отримує кілька шматочків (можливо, один), що йдуть у масиві один за одним (неперервний блок).
Сумарна вага шматочків у кожній порції має бути однаковою.
Всього пиріг ділиться на k+1 рівну частину (тобто сам Василько та друзів). Завдання задачі полягає в тому, щоб знайти максимальне число (кількість друзів), при якому такий поділ можливий. Зверніть увагу, що кожен шматок має бути у якісь порції.
Допоможіть Васильку порахувати, яку максимальну кількість друзів він може запросити на пікнік.
Перший рядок містить одне число (1 \le n \le 5000) — кількість кусочків пирога.
Другий рядок містить цілих чисел a_{1}, a_2, \dots, a_{n} (1 \le a_{i} \le 10^4) — вага кожного кусочка пирога.
Одне ціле число, максимальну кількість друзів, котрих може запросити Василько.
Example 1
Example 2
У першому прикладі він може розділити пиріг на частин, де вага кожної частини буде . Це можна зробити, наприклад, так: 1+3, , 2+2, 3+1, , 1+1+2. Оскільки буде всього частин, то він може запросити лише друзів.
У другому прикладі він може лише розділити пиріг на частину (весь пиріг). У такому випадку він не може запросити друзів.