P17579 [JAG 2026 Summer Camp #3] Noise Cancelling

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 $$ x_i+x_{i+m}=0 $$ 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.

The input consists of a single test case of the following format. ```text 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.

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