本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-02-02 05:25:48

考虑到我们可以枚举中间值，然后要求的就是在每个元素之前，小于这个元素以及大于这个元素的元素数量。用乘法原理即可得到最后答案。

形式化地，我们设 $l_i$ 是 $1$ 到 $i - 1$ 中小于 $x_i$ 的元素数量，$r_i$ 对称，那么最终答案就是 $\sum\limits_{i=1}^{n} l_i\times r_i$。

那么我们就是要求参数 $l_i$ 与 $r_i$。考虑离线 + 离散化 + 树状树组。这里树状树组实际上就是个桶前缀和。

然后做法明显。