A Little Bit of Formal Statements Never Hurt Anybody

You are given an array of pairwise distinct integers $a_1,a_2,\dots ,a_n$.

Count the number of pairs $(l,r)$ $(1\le l\le r\le n)$ where $a_l+\cdots +a_k=a_k+\cdots +a_r$ and $k$ is the position of the maximum element among $a_l,a_{l+1},\dots ,a_{r-1},a_r$.

Input

The first line contains a single integer $n$ ($1\le n\le 3\cdot 10^5$) — the length of the array $a$.

The second line contains $n$ integers $a_1,a_2,\dots ,a_n$ ($-10^9\le a_i\le 10^9$) — elements of the array $a$.

It is guaranteed that all integers in the array are pairwise distinct.

Output

Output a single integer — the amount of pairs $(l,r)$ described in the statement.

Examples

Note

In the first example, the array is $a=[1,3,5,4,2]$. There are $6$ pairs $(l,r)$ which satisfy the statement:

1. $l=1$, $r=4$; in this case $k$ equals $3$, because $5$ is the maximum between $[1,3,5,4]$; the pair $l=1$, $r=4$ holds the statement, since $1+3+5=5+4$;

2. $l=1$, $r=1$;

3. $l=2$, $r=2$;

4. $l=3$, $r=3$;

5. $l=4$, $r=4$;

6. $l=5$, $r=5$.

Scoring

1. ($3$ points): $n\le 100$;

2. ($7$ points): $n\le 10^3$;

3. ($13$ points): $a_1<a_2<\cdots <a_n$;

4. ($8$ points): there exists $i$ $(1\le i\le n)$, such that $a_1<\cdots <a_i$ and $a_i>\cdots >a_n$;

5. ($22$ points): $n\le 10^5$;

6. ($23$ points): array consists of random integers $(-10^9\le a_i\le 10^9)$;

7. ($24$ points): no additional restrictions.