시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 256 MB | 3 | 0 | 0 | 0.000% |
Однажды Антон Сергеевич рассказывал студентам алгоритм построения трапецоидных карт. В качестве разминки он дал им задачу о трапециях. Он нарисовал на доске n отрезков. Длина i-го отрезка равна ai. Студентам требуется найти количество различных наборов из четырех отрезков, из которых можно составить равнобедренную трапецию ненулевой площади.
Напомним, что равнобедренная трапеция — это четырехугольник, две противоположных стороны которого параллельны, а две других — равны. Пример равнобедренной трапеции приведен на рисунке.
Два набора считаются различными, если существует отрезок, принадлежащий первому набору и не принадлежащий второму. Номера взятых отрезков в каждом наборе должны быть попарно различными.
Помогите студентам найти количество таких наборов.
В первой строке задано число t — столько раз Антон давал своим студентам эту задачу. В следующих 2t cтроках содержится описания всех задач.
Описание каждой задачи состоит из двух строк. В первой строке описания дано число n — количество отрезков, нарисованных на доске. Во второй строке описания задачи дано n целых чисел ai — их длины (4 ≤ n ≤ 5000, 1 ≤ ai ≤ 108 для всех i от 1 до n).
Суммарное число всех отрезков во всех задачах не превышает 5000.
Для каждой задачи в отдельной строке выведите одно число — искомое количество наборов.
2 4 3 9 5 5 6 1 1 1 1 1 1
1 15