Hello 2016Ended |
Usted recibe una secuencia de $n$ números $A_0, ..., A_{n-1}$. Un corrimiento cíclicos de $k$ posiciones $(0 \le k \le n - 1)$ termina en la siguiente secuencia $A_k, A_{k+1}, ..., A_0, A_1, ..., A_{k-1}$.
El problema que queremos resolver es cuántos corrimientos cíclicos satisfacen la condición que la suma de los primeros $i$ números es mayor o igual que cero para todos los $i$ $(1 \le i \le n)$.
Cada caso consiste de dos líneas.
La primera contiene el número $n$ $(1\le n \le 1000000)$, el número de enteros en la secuencia.
La segunda contiene $n$ enteros $A_0, ..., A_{n-1}$ $(-1000 \le A_i \le 1000)$ representando la sequencia de números. La entrada termina con una línea que contiene $0$.
* La cantidad de casos $T$ es $(T \leq 105)$.
Para cada caso imprima una línea, el número de corrimientos cíclicos que satisfacen la condición.