P12931 [NOISG 2020 Prelim] Mountains

企鹅 Pengu 和他的朋友们生活在南极洲。虽然企鹅不会飞，但他们渴望体验翱翔天际的感觉。为了满足大家的愿望，Pengu 决定借助科技的力量——滑翔伞。

幸运的是，在南极横贯山脉中有 $n$ 座山峰。这些山峰从左到右依次编号为 $1$ 到 $n$，第 $i$ 座山峰的高度为 $H_i$。 Pengu 决定选择三座山峰 $x,y,z$，他打算在山峰 $y$ 上建立起飞站，在山峰 $x$ 和 $z$ 上分别设置接收站。企鹅们将从山峰 $y$ 滑翔至山峰 $x$ 或 $z$。 为了容纳更多企鹅并避免空中相撞，山峰 $x$ 必须位于山峰 $y$ 左侧，山峰 $z$ 必须位于山峰 $y$ 右侧，并且山峰 $x$ 和 $z$ 的高度必须都**严格小于**山峰 $y$。 Pengu 非常严谨，他想统计所有满足条件的选择方案。请你帮他计算，满足以下条件的三元组 $(x,y,z)$ 有多少个： - $1 \leq x < y < z \leq n$； - $H_x < H_y$ 且 $H_z < H_y$。

第一行包含一个整数 $n$，表示山峰的数量。 第二行包含 $n$ 个整数，第 $i$ 个整数表示第 $i$ 座山峰的高度 $H_i$。

输出一个整数，表示满足条件的方案总数。

【样例解释】 对于样例 #1： - 共有 $2$ 组满足条件的三元组：$(1,2,4)$、$(1,3,4)$。 对于样例 #2： - 共有 $7$ 组满足条件的三元组：$(1,3,4)$、$(1,3,6)$、$(1,5,6)$、$(2,3,4)$、$(2,3,6)$、$(2,5,6)$、$(4,5,6)$。 【数据范围】 - $3 \leq n \leq 3 \times 10^5$； - $0 \leq H_i \leq 10^{18}$。 | 子任务编号 | 分值 | 额外限制 | | :--------: | :--: | :-------------------------------------------------: | | $1$ | $2$ | $H_i$ 单调不减（即 $H_i \leq H_j$，对任意 $i < j$） | | $2$ | $4$ | $0 \leq H_i \leq 1$ | | $3$ | $9$ | $0 \leq H_i \leq 99$ | | $4$ | $36$ | $n \leq 500$ | | $5$ | $28$ | $n \leq 10^4$ | | $6$ | $9$ | $0 \leq H_i \leq 10^5$ | | $7$ | $12$ | 无额外限制 |