题目描述

“V 字形” 是一种重要的阵形密码，在《孙子兵法》中被称为 “鹤翼阵”，其形态为 “中间低，两侧高”，象征着合围之势。现在，一支古代军队的布阵记录被发现了。

在古战场上，有 $n$ 个阵地从左到右依次排开，第 $i$ 个阵地的兵力记为 $a_i$ 。

军师发现，如果存在三个阵地 $i < j < k$ ，其兵力恰好满足： $a_i>a_j<a_k$ 。

也就是中间阵地的兵力比两侧都少，那么就形成了一个 “V 字形阵”，也称鹤翼阵。

你的任务是统计这个阵形记录中，不同的 “V 字形阵” 一共有多少个。

输入格式

第一行一个整数 $n$ ，表示阵地的数量。

第二行 $n$ 个整数 $a_1, a_2, ..., a_n$ ，表示各阵地的兵力。

输出一个整数，表示不同的 $(i,\ j,\ k)$ 三元组数量，满足 $i < j < k$ 且 $a_i > a_j < a_k$ 。

5
5 1 4 2 3

满足条件的有 $\{5,\ 1,\ 4\}$ ， $\{5,\ 1,\ 2\}$ ， $\{5,\ 1,\ 3\}$ ， $\{5,\ 2,\ 3\}$ ， $\{4,\ 2,\ 3\}$ 。

对于 $70\%$ 的数据， $3\le n\le 500$ 。

对于 $100\%$ 的数据， $3\le n \le 5000$ ， $1\le a_i\le 5000$ 。