SP9650 TRIPINV - Mega Inversions

对于任何排序算法，$n^2$ 的复杂度上界很容易理解：只需要取出两个顺序错误的元素并交换它们。Conrad 提出了一种新的算法，这种算法不再局限于交换两个元素，而是处理三个不按顺序排列的元素。具体来说，找到三个元素 $a_i > a_j > a_k$ 且 $i < j < k$，然后将它们重新排列成 $a_k, a_j, a_i$ 的顺序。如果说原有算法的步骤数量由最多的逆序对数 $\frac{n(n-1)}{2}$ 来限制，那么 Conrad 想知道在一个给定的序列中，这种三元组的上界是多少。为了帮助他，你需要编写一个程序来计算这些三元组的数量。

第一行输入的是序列的长度 $1 \le n \le 10^5$。 第二行输入一个整数序列 $a_1, a_2, \ldots, a_n$。 可以假设所有的 $a_i$ 都在 $[1, n]$ 范围内。

输出不按顺序排列的三元组数量。 **本翻译由 AI 自动生成**