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.