D-涂色游戏

题目描述

Alice 和 Bob 使用一个长度为 $n$ 的数列 $a$ 进行游戏。

初始时，任何数列中的数字都没有被染色。首先，Alice 选择 $3$ 个 $a$ 中的元素并将它们染为红色。然后 Bob 将选择一个任意元素并将它染为蓝色（如果这个元素原本是红色的，那么蓝色将覆盖掉红色）。Alice 获胜当且仅当剩余的红色的数字之和严格大于蓝色的数字。

你需要计算 Alice 有多少种选择 $3$ 个元素染色的方案使得无论 Bob 如何操作 Alive 都将获胜。

输入格式

多组数据。第一行一个整数 $t$ ($1\le t\le 1000$) 表示数据组数。

对于每组数据，第一行一个整数 $n$ ($3\le n\le 5000$)。
第二行 $n$ 个整数 $a_1,a_2,\cdots,a_n$ ($1\le a_1\le a_2\le \cdots\le a_n\le 10^5$)。

保证单个测试点内 $\sum n\le 5000$。

输出格式

对于每组数据，输出一行一个整数表示答案。

输入输出样例 #1

输入 #1

6
3
1 2 3
4
1 1 2 4
5
7 7 7 7 7
5
1 1 2 2 4
6
2 3 3 4 5 5
5
1 1 1 1 3

输出 #1

0
0
10
2
16
0

说明/提示

样例解释

对于前两组数据，无论 Alice 怎么选择元素，Bob 总有办法选择元素使得 Alice 不能获胜。

对于第三组数据，Alice 可以选择任意的三个元素。如果 Bob 选择对红色的某个元素染色，红色数字的和将为 $14$，蓝色数字的和将为 $7$；如果 Bob 选择对某个未染色的元素染色，红色数字的和将为 $21$，蓝色数字的和将为 $7$。

对于第四组数据，Alice 可以选择 $a_1,a_3,a_4$ 或 $a_2,a_3,a_4$。