[R58D]双胞胎周长 - 代码源竞赛平台

时空限制

1S/512M

题目描述

给定一个长度为 $n$ 的正整数数组 $a$，保证数组中所有元素模 $3$ 同余，即对于任意的 $i,j$，$a_i \bmod 3 = a_j \bmod 3$。

定义 $s_i$ 为周长等于 $a_i$ 且三边长均为正整数的三角形的个数。

若两个下标 $i$ 和 $j$ 满足 $1 \leq i < j \leq n$ 且 $s_i = s_j$，则称 $(a_i, a_j)$ 是一对“双胞胎周长”。 请你计算出数组 $a$ 中共有多少对“双胞胎周长”。

注意：三条边长对应相等的三角形视为同一个三角形（即不考虑旋转和翻转）。

格式

输入格式

第一行包含一个正整数 $n$，表示数组的长度。

第二行包含 $n$ 个数 $a_1 ,a_2 ,a_3 ,\cdots a_n$，表示 $a$ 数组。

输出格式

输出一行，表示 $a$ 数组中“双胞胎周长”的对数。

样例

样例输入 #1

10
3 6 6 3 9 12 9 24 99 99

样例输出 #1

10

样例输入 #2

10
5 5 5 5 5 8 8 8 8 8

样例输出 #2

45

样例输入 #3

10
3 9 15 21 27 33 39 45 51 57

样例输出 #3

0

数据规模

注意：你只有通过了子任务的所有测试点，才能获得对应子任务的分数。

子任务编号	分数	$n \leq$	$a_i \leq$
$1$	$40$	$5000$	$100$
$2$	$60$	$2 \times 10^5$	$10^9$

对于 $100\%$ 的数据，保证 $1 \leq n \leq 2 \times 10^5,1 \leq a_i \leq 10^9$。数组中所有元素模 $3$ 同余。