You are given a sequence of \textbf{n} numbers \textbf{a_0}, ..., \textbf{a_\{n-1\}}. A cyclic shift by \textbf{k} positions (\textbf{0} ≤ \textbf{k} ≤ \textbf{n-1}) results in the following sequence: \textbf{a_k}, \textbf{a_\{k+1\}}, ..., \textbf{a_\{n-1\}}, \textbf{a_0}, \textbf{a_1}, ..., \textbf{a_\{k-1\}}. How many of the \textbf{n} cyclic shifts satisfy the condition that the sum of the fi rst \textbf{i} numbers is greater than or equal to zero for all \textbf{i} with \textbf{1} ≤ \textbf{i} ≤ \textbf{n}? \InputFile Each test case consists of two lines. The fi rst contains the number \textbf{n} (\textbf{1} ≤ \textbf{n} ≤ \textbf{10^6}), the number of integers in the sequence. The second contains \textbf{n} integers \textbf{a_0}, ..., \textbf{a_\{n-1\}} (\textbf{-1000} ≤ \textbf{a}_i ≤ \textbf{1000}) representing the sequence of numbers. The input will finish with a line containing \textbf{0}. \OutputFile For each test case, print one line with the number of cyclic shifts of the given sequence which satisfy the condition stated above.