题目描述

现在给你一个长度为 n 的正整数数组。数组中的每个数字满足 $1≤a_i≤n$ 。

我们知道，对每个正整数而言，它具有许多个因数。例如 6 具有因数 {1,2,3,6} ，共 4 个不同的因数；4 具有因数 {1,2,4} ，共 3 个不同的因数。

你需要求出，有多少不同的子数组，使得子数组内的数字异或和的因数数量是偶数个。

特别地，在本题中，由于 0 不具备因数，因此异或和为零的子数组不考虑在内。

两个子数组被视为不同的，当且仅当两个子数组的起止范围至少有一个是不同的。

输入格式

一行一个正整数 n ，表示数组的长度。

接下来一行 n 个正整数，依次表示数组中的每个数字。

输出格式

一行一个整数表示答案。

输入输出样例 #1

输入 #1

3
3 1 2

输出 #1

4

说明/提示

样例解释

下列4个子数组的异或和的因数数量是偶数个：[3], [3,1], [1,2], [2].

数据范围

$1 \le n \le 200000$