题目描述

你面前的桌子上，摆着一个 $n$ 个数的数组 $A$。

如果一个子区间，满足每个数都只出现了奇数次，那么它是个好区间。

那么这个数组有多少个好区间呢？

输入格式

一行一个数字 $n$。

一行 $n$ 个数字，表示数组 $A$。

输出格式

一行一个数字表示答案。

样例

input

4
2 2 2 3

output

7

数据范围与提示

对于 $20\%$ 的数据，满足 $n \leq 1000$。

对于 $40\%$ 的数据，满足 $n \leq 5 \times 10^4$。

对于另外 $10\%$ 的数据，满足 $a_i \leq 5$。

对于另外 $20\%$ 的数据，满足 $a_i \leq 64$。

对于 $100\%$ 的数据，满足 $n \leq 2 \times 10^5, a_i \leq 10^6$。