题目描述

对于一个由非零整数组成的序列 $X$，如果存在一个正整数 $m$，使得它的长度为 $2m$，并且对于每个 $i$（$1\le i\le m$）都有

则称该序列是消噪序列，其中 $x_i$ 表示 $X$ 的第 $i$ 个元素。换言之，消噪序列的后半部分是其前半部分逐项取相反数后得到的序列，因此对应的元素可以相互抵消。特别地，任何长度为奇数的序列都不是消噪序列。

例如，$(1,2,-3,4,-1,-2,3,-4)$ 是消噪序列。

给定一个由 $N$ 个非零整数组成的序列 $(a_1,a_2,\ldots,a_N)$。求满足连续子序列 $(a_l,a_{l+1},\ldots,a_r)$ 是消噪序列的整数对 $(l,r)$（$1\le l\le r\le N$）的数量。

输入格式

输入包含一组测试数据，格式如下。

N
a_1 a_2 ... a_N

第一行包含一个整数 $N$（$1\le N\le2\times10^5$），表示序列的长度。

第二行包含 $N$ 个非零整数 $a_1,a_2,\ldots,a_N$（$1\le |a_i|\le N$），表示序列中的元素。

输出格式

输出一个整数，表示使得 $(a_l,a_{l+1},\ldots,a_r)$ 为消噪序列的整数对 $(l,r)$ 的数量。

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