Ogni giorno, durante la passeggiata nella fattoria, la mucca Bessie visita il suo pascolo preferito, che ha $N$ fiori (tutte margherite colorate), numerati $1\ldots N$ e disposti in fila ($1\le N \le 100$). Il fiore $i$ ha $p_i$ petali ($1 \le p_i \le 1000$).

Come fotografa alle prime armi, Bessie decide di scattare diverse foto di questi fiori. In particolare, per ogni coppia di fiori $(i,j)$ con $1\le i\le j\le N$, fotografa tutti i fiori dal fiore $i$ al fiore $j$ (inclusi $i$ e $j$).

Più tardi, Bessie guarda le foto e nota che alcune hanno un «fiore medio»: un fiore con $P$ petali, dove $P$ è la media esatta del numero di petali di tutti i fiori della foto.

Quante foto di Bessie hanno un fiore medio?

Input

La prima riga contiene $N$. La seconda contiene $N$ interi $p_1 \dots p_N$ separati da spazi.

Output

Stampa il numero di foto che hanno un fiore medio.

Esempi

Input 1

4
1 1 2 3

Output 1

6

Nota

Ogni foto con un solo fiore contribuisce al conteggio (nell’esempio sono quattro). Inoltre, gli intervalli $(i,j)$ uguali a $(1,2)$ e $(2,4)$ corrispondono anch’essi a foto con un fiore medio.

Autore del problema: Nick Wu