У 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\).
Выходные данные
Для каждого набора входных данных выведите одно целое число — количество различных наборов индексов \([a,b,c,d]\).
Примечание
В первом наборе входных данных имеется \(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]\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|