Extrato

Flúcio está analisando seu extrato bancário, formado de depósitos e saques. No extrato, depósitos são representados como números positivos e saques como negativos, sem existir uma transação de valor $0$.

Flúcio não gosta do valor $0$, e portanto deseja que em nenhum intervalo contínuo de tempo, o valor, definido como $soma dos depósitos + soma dos saques$ (note que os saques são números negativos), do extrato considerando apenas as transações nesse intervalo seja $0$.

Esse desejo no entanto, nem sempre é possível com o extrato original. Flúcio está se perguntando, se pudesse adicionar transições com valores arbitrários (podendo ser muito muito grandes ou pequenos, $0$, sem necessariamente ser suportado por uma linguagem de programação), entre duas transições seguidas, quantas transições precisariam ser adicionadas para que não houvesse nenhum intervalo de valor $0$.

Sua tarefa nesse problema é encontrar o número mínimo de transações para realizar o desejo de Flúcio.

Entrada:

A primeira linha da entrada contém um inteiro $n$, o número de transações no extrato de Flúcio.

A segunda linha da entrada contém $n$ inteiros $t_1, t_2, t_3$ ... $t_n$, as transações no extrato.

Saída:

A saída deve conter um inteiro, o número de transações para que o desejo de lúcio seja realizado.

Restrições:

• $2 \leq n \leq 2*10^5$
• $-10^9 \leq t_i \leq 10^9$$

Exemplos:

4
1 -5 3 2

1

5
4 -2 3 -9 2

0

9
-1 1 -1 1 -1 1 1 -1 -1

6

8
16 -5 -11 -15 10 5 4 -4

1

Para submeter sua solução, use esse link.