Problema B - Barragem equilibrada

O sistema de barragens da Meireles Lda é do mais avançado que há no país para protejer as cidades de cheias ao mesmo tempo que produz energia elétrica para alimentar as mesmas. A tecnologia inovadora da Meireles Lda consiste em colocar várias mini barreiras ao longo do rio, de forma a distribuir a água por uma área maior.

Um sistema de barragens é constituído por um conjunto de zonas de água e de barreiras, dispostos em linha, num total de N zonas e barreiras. Cada zona de água tem um inteiro atribuido, que representa o quão agitado é o rio nessa zona. Adicionalmente, cada barreira tem um inteiro atribuido, que representa o quão resistente é a barreira.

Para simplificar, representamos um rio como uma sequência S de N inteiros positivos e negativos (sem zeros), onde os inteiros positivos representam barreiras e os negativos zonas de água. Ou seja, uma barreira com o valor de 5 atribuido é representada em S como 5 e uma zona de água com o valor de 3 atribuido é representada em S como -3. Por exemplo, se considerarmos o sistema: S = 2, -4, 5, -3, -9, 7, -3, -1, 4, com N = 9, temos o seguinte sistema:

A ação das barreiras é feita em pares, ou seja, cada par de barreiras interage de forma a controlar o rio. Para um par de barreiras i, j (ou seja, S_i e S_j são positivos), dizemos que o par é equilibrado se:

• i < j;
• O valor absoluto da soma dos valores de todas as zonas de água entre i e j é menor ou igual a S_i + S_j, ou seja, à soma dos valores das barreiras i e j;

Por exemplo, o par constituído pela segunda e terceira barreira é equilibrado, visto que a soma dos seus valores é 12 e no meio deles apenas há duas zonas de água, com soma total -12, e temos que 12 é menor ou igual a 12. Por sua, vez, a primeira e terceira barreira não formam um par equilibrado, visto que a sua soma é 9 e as três zonas de água entre elas somam -16, e temos que 16 é maior que 9.

Para garantir que o sistema de barragens é estável, é necessário que o número de pares de barreiras equilibradas seja maior que um certo valor, que depende de vários fatores (condições climatéricas, etc). Como tal, a Meireles Lda precisa de uma forma eficiente de calcular o número de pares equilibrados de um sistema de barragens, de forma a poder fazer decisões sobre o seu funcionamento. Consegues ajudá-la?

O Problema

Dado uma sequência de N barreiras e zonas de água, calcular o número de pares de barreiras equilibradas.

Input

A primeira linha contém um inteiro, N, representando o número de barreiras e zonas de água.

Segue-se uma linha, contendo N inteiros, representando as barreiras e zonas de água.

É garantido que a sequência não contém nenhum valor 0.

Output

O output deve conter um inteiro, que representa o número de pares de barreiras equilibradas.

Nota: a resposta tem valor máximo 2⁶⁰

Restrições

São garantidos os seguintes limites em todos os casos de teste que irão ser colocados ao programa:

Os casos de teste deste problema estão organizados em 4 grupos com restrições adicionais diferentes:

Input do Exemplo 1

9
2 -4 5 -3 -9 7 -3 -1 4

Output do Exemplo 1

3

Explicação do Exemplo 1

Este exemplo corresponde ao mencionado no enunciado.

Input do Exemplo 2

12
-10 1 2 -9 4 5 6 -3 -4 8 -1 -15

Output do Exemplo 2

7

Input do Exemplo 2

13
1 -1 2 -3 4 -5 7 -8 9 -9 10 -1 11

Output do Exemplo 2

12