Ненегативні Часткові Суми
Вам надано послідовність з n чисел a_0, ..., a_{n-1}. Циклічний зсув на k позицій (0 ≤ k ≤ n-1) утворює таку послідовність: a_k, a_{k+1}, ..., a_{n-1}, a_0, a_1, ..., a_{k-1}. Потрібно визначити, скільки з n циклічних зсувів задовольняють умову, що сума перших i чисел є більшою або дорівнює нулю для всіх i з 1 ≤ i ≤ n.
Вхідні дані
Кожен тестовий випадок складається з двох рядків. Перший рядок містить число n (1 ≤ n ≤ 10^6), яке вказує на кількість цілих чисел у послідовності. Другий рядок містить n цілих чисел a_0, ..., a_{n-1} (-1000 ≤ a_i ≤ 1000), що представляють саму послідовність. Вхідні дані завершуються рядком, що містить 0.
Вихідні дані
Для кожного тестового випадку виведіть один рядок, що містить кількість циклічних зсувів даної послідовності, які задовольняють зазначену умову.