問題文

高橋君は A_1, A_2, \cdots, A_N の N 要素からなる整数列 A を持っています。

A_i < A_j > A_k を満たす (i, j, k) (1 \leq i < j < k \leq N) の組の個数を求めてください。

制約

• 3 \leq N \leq 5000
• 0 \leq A_i \leq 10^9
• 入力は全て整数である

入力例 1

4
1 2 3 2

出力例 1

2

条件を満たす組は (i, j, k) = (1, 3, 4), (2, 3, 4) の 2 つがあります。

入力例 2

3
2 2 2

出力例 2

0

A_i < A_j > A_k を満たす (i, j, k) の組はありません。

入力例 3

10
0 7 7 6 9 8 1 3 2 0

出力例 3

57