Ненегативные Частичные Суммы
Вам дана последовательность из 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.
Выходные данные
Для каждого тестового случая выведите одну строку, содержащую количество циклических сдвигов данной последовательности, которые удовлетворяют указанному выше условию.