시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 (추가 시간 없음) | 512 MB | 57 | 28 | 27 | 55.102% |
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 ai.
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 aj − ai = ak − aj 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 ≤ t ≤ 10). Then t test case descriptions follow.
The first line of a test case contains an integer n — the number of the days (3 ≤ n ≤ 2000). The second line of the test case contains n integers a1, a2, . . . , an, where ai is the difficulty of the problem on the i-th day (1 ≤ ai ≤ 109).
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 ≤ i < j < k ≤ n and ak − aj = aj − ai.
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