Arithmetic Sequence

发布时间: 2018年8月14日 17:33   最后更新: 2018年8月14日 17:35   时间限制: 2000ms   内存限制: 256M

CSL给了你一个长度为$n$的序列$a_1,a_2,\ldots,a_n$,你需要从中选择三个数$(i,j,k)$,($i < j < k$),使得$a_i,a_j,a_k$在某种排列下是等差序列。

那么你有多少种选法呢?

第一行是一个整数$T$,表示测试数据的组数。
对于每组数据:
第一行是一个整数$n$,表示序列的长度。
第二行是$n$个数$a_1,a_2,\ldots,a_n$。
$T \leq 100$
$1 \le n \le 10 ^ {5}$
$1 \le a_i \le 1000$
$\sum n \le 2 \times 10 ^ {6}$

对于每组测试数据,在一行内输出一个整数表示不同的方案数。

复制
3
5
1 2 3 3 3
3
2 1 3
4
1 1 1 1
4
1
4

第一个样例:方案为$(1,2,3),(1,2,4),(1,2,5),(3,4,5)$。

第二个样例:方案为$(1,2,3)$。

第三个样例:方案为$(1,2,3),(1,2,4),(1,3,4),(2,3,4)$。

math

ACM集训队暑期集训新生组队赛