好二元组

题目描述

给定一个长度为 n 的数组 a_0, a_1, ..., a_{n-1}。称一对不同的下标 (i, j) 为好二元组，当且仅当满足以下条件：

• 0 <= i < j <= n - 1
• 2 * i <= j
• a_i xor a_j = 0

其中 xor 表示按位异或运算。

请计算数组中满足条件的好二元组数量。

输入格式

第一行输入一个整数 n。

第二行输入 n 个整数，表示数组 a。

输出格式

输出一个整数，表示好二元组的数量。

数据范围

1 <= n <= 2 * 10^5

1 <= a_i <= n

样例 1

输入

4
1 1 1 1

输出

5

说明

满足条件的下标对共有 5 个，分别为 (0, 1)、(0, 2)、(0, 3)、(1, 2)、(1, 3)。