난이도 관리

면접 대비

시간 제한2초메모리 제한512 MB

요약
i < j < k인 세 인덱스에서 a[j] - a[i]와 a[k] - a[j]가 같아지는, 즉 a[i] + a[k] = 2*a[j]인 삼중항의 개수를 센다.
난이도

보통10점 중 5점

유형
해시맵, 조합론, 배열, 완전 탐색
정답자
아직 제출이 없습니다

문제

Codehorses에는 매일 새로운 프로그래밍 문제가 하나씩 올라온다. 따라서 앞으로 n일 동안 n개의 문제가 올라오게 되며, i번째 문제의 난이도는 ai이다.

Polycarp은 세 날 i, j, k (i < j < k)를 골라서 j일과 i일의 난이도 차이가 k일과 j일의 난이도 차이와 같도록 만들고 싶다. 다시 말해 aj − ai = ak − aj가 성립하기를 원한다.

Polycarp이 원하는 방식으로 세 날을 고를 수 있는 경우의 수를 구하라.

입력

첫째 줄에는 입력에 주어지는 테스트 케이스의 수 t가 주어진다 (1 ≤ t ≤ 10). 이어서 t개의 테스트 케이스가 주어진다.

테스트 케이스의 첫째 줄에는 날의 수 n이 주어진다 (3 ≤ n ≤ 2000). 테스트 케이스의 둘째 줄에는 n개의 정수 a1, a2, . . . , an이 주어지며, ai는 i번째 날에 올라온 문제의 난이도이다 (1 ≤ ai ≤ 109).

출력

입력에 주어진 순서대로 각 테스트 케이스의 답을 나타내는 t개의 정수를 출력한다. 테스트 케이스의 답은 1 ≤ i < j < k ≤ n이고 ak − aj = aj − ai인 인덱스 삼중쌍 i, j, k의 개수이다.

예제1

  1. 예제 1

    입력
    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