406452: GYM102411 M Managing Difficulties

Every day a new programming problem is published on Codehorses. Thus, $$$n$$$ problems will be published in the following $$$n$$$ days: the difficulty of the $$$i$$$-th problem is $$$a_i$$$.

Polycarp wants to choose exactly three days $$$i$$$, $$$j$$$ and $$$k$$$ ($$$i < j < k$$$) so that the difference of difficulties on the day $$$j$$$ and the day $$$i$$$ is equal to the difference of difficulties on the day $$$k$$$ and day $$$j$$$. In other words, Polycarp wants equality $$$a_j-a_i=a_k-a_j$$$ to be true.

Determine the number of possible ways for Polycarp to choose the three days in the desired way.

The first line contains an integer $$$t$$$ — the number of test cases in the input ($$$1 \le t \le 10$$$). Then $$$t$$$ test case descriptions follow.

The first line of a test case contains an integer $$$n$$$ — the number of the days ($$$3 \le n \le 2000$$$).

The second line of the test case contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$, where $$$a_i$$$ is the difficulty of the problem on the $$$i$$$-th day ($$$1 \le a_i \le 10^9$$$).

Output $$$t$$$ integers — the answers for each of the test cases in the input, in the order they are given. The answer to a test case is the number of triples of indices $$$i$$$, $$$j$$$, and $$$k$$$ such that $$$1 \le i < j < k \le n$$$ and $$$a_k-a_j=a_j-a_i$$$.

4
5
1 2 1 2 1
3
30 20 10
5
1 2 2 3 4
9
3 1 4 1 5 9 2 6 5

1
1
4
5