A. Tokitsukaze и странное неравенство
ограничение по времени на тест
1.5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Tokitsukaze есть перестановка $$$p$$$ длины $$$n$$$. Напомним, что перестановкой $$$p$$$ длины $$$n$$$ называется последовательность $$$p_1, p_2, \ldots, p_n$$$, состоящая из $$$n$$$ различных целых чисел, каждое из которых от $$$1$$$ до $$$n$$$ ($$$1 \leq p_i \leq n$$$).

Она хочет знать, сколько различных наборов индексов $$$[a,b,c,d]$$$ ($$$1 \leq a < b < c < d \leq n$$$) в этой перестановке удовлетворяют следующим двум неравенствам:

$$$p_a < p_c$$$ и $$$p_b > p_d$$$.

Обратите внимание, что два набора $$$[a_1,b_1,c_1,d_1]$$$ и $$$[a_2,b_2,c_2,d_2]$$$ считаются различными, если $$$a_1 \ne a_2$$$, или $$$b_1 \ne b_2$$$, или $$$c_1 \ne c_2$$$, или $$$d_1 \ne d_2$$$.

Входные данные

Первая строка содержит одно целое число $$$t$$$ ($$$1 \leq t \leq 1000$$$) — количество наборов входных данных. Каждый набор входных данных состоит из двух строк.

В первой строке записано одно целое число $$$n$$$ ($$$4 \leq n \leq 5000$$$) — длина перестановки $$$p$$$.

Вторая строка содержит $$$n$$$ целых чисел $$$p_1, p_2, \ldots, p_n$$$ ($$$1 \leq p_i \leq n$$$) — перестановка $$$p$$$.

Гарантируется, что сумма $$$n$$$ по всем тестам не превышает $$$5000$$$.

Выходные данные

Для каждого набора входных данных выведите одно целое число — количество различных наборов индексов $$$[a,b,c,d]$$$.

Пример
Входные данные
3
6
5 3 6 1 4 2
4
1 2 3 4
10
5 1 6 2 8 3 4 10 9 7
Выходные данные
3
0
28
Примечание

В первом наборе входных данных имеется $$$3$$$ различных набора $$$[a,b,c,d]$$$.

$$$p_1 = 5$$$, $$$p_2 = 3$$$, $$$p_3 = 6$$$, $$$p_4 = 1$$$, где $$$p_1 < p_3$$$ и $$$p_2 > p_4$$$ удовлетворяет неравенству, поэтому один из $$$[a,b,c,d]$$$ наборов — это $$$[1,2,3,4]$$$.

Точно так же два других набора — это $$$[1,2,3,6]$$$ и $$$[2,3,5,6]$$$.