题解

题面描述

给定一个长度为 $n$ 的数组 $\{a_1, a_2, \dots, a_n\}$，定义数对 $\{x, y\}$ 为一对“好数”，当且仅当 $x, y, x \oplus y$ 这三个数能够作为三条边，构成一个非退化的三角形。

求有多少对下标 $(i, j)$ 满足 $1 \le i < j \le n$，且 $\{a_i, a_j\}$ 是一对“好数”。

其中，$\oplus$ 表示按位异或操作。

题目内容

小红定义一个数对 {$x,y$} 是一对"好数”，当且仅当 $x,y,x⊕y$ 这三个数能作为三条边，构成一个非退化的三角形。

现在小红拿到了一个数组 ${a_1,a_2,…,a_n}$ ，她希望你求出有多少对下标 $(i,j)$ 满足 $1≦i<j≦ n$ ，且对应的值 {$a_i, a_j$} 是一对"好数”。

在这里，⊕ 表示位运算中的按位异或操作。

输入描述

第一行输入一个正整数 $n$ ，代表数组大小。

第二行输入 $n$ 个正整数$a_i$ ，代表数组的元素。

$1≦n≦10^5$

$1≦a_i ≦1000$

输出描述

一个整数，代表满足 {$a_i,a_j$} 是好数的 $(i,j)$ 对儿数。

样例1

输入

4
2 3 4 5

输出

1

说明

在这个样例中，只能找到唯一的一对下标 $i= 2、j= 4$ ，构成好数：{$3,5$} 。

样例2

输入

5
5 6 5 6 7

输出

4