Problem Description

A sequence $X$ consisting of nonzero integers is called noise-cancelling if there exists a positive integer $m$ such that its length is $2m$ and

holds for every $i$ ($1\le i\le m$), where $x_i$ denotes the $i$-th element of $X$. In other words, the second half of a noise-cancelling sequence is the elementwise negation of its first half, so the corresponding elements cancel each other out. In particular, no sequence of odd length is noise-cancelling.

For example, $(1,2,-3,4,-1,-2,3,-4)$ is noise-cancelling.

You are given a sequence of $N$ nonzero integers $(a_1,a_2,\ldots,a_N)$. Find the number of pairs of integers $(l,r)$ ($1\le l\le r\le N$) such that the contiguous subsequence $(a_l,a_{l+1},\ldots,a_r)$ is noise-cancelling.

Input Format

The input consists of a single test case of the following format.

N
a_1 a_2 ... a_N

The first line contains an integer $N$ ($1\le N\le2\times10^5$), representing the length of the sequence.

The second line contains $N$ nonzero integers $a_1,a_2,\ldots,a_N$ ($1\le |a_i|\le N$), representing the elements of the sequence.

Output Format

Print a single integer representing the number of pairs $(l,r)$ such that $(a_l,a_{l+1},\ldots,a_r)$ is noise-cancelling.

9
1 -3 2 -2 -1 3 -2 2 -2

4

20
-1 -1 -1 1 1 1 -1 -1 1 1 -1 -1 -1 1 1 -1 1 -1 -1 1

26