问题描述

在一个遥远的魔法世界中，有一个古老的魔法塔。魔法塔的主人是一位智慧无比的老魔法师，他每年都会挑选一些年轻的魔法学徒进行试炼，只有通过了试炼的学徒才能获得进入塔顶的资格，学习更高深的魔法。

今年，魔法塔迎来了来自各地的学徒。老魔法师为了测试这些学徒的智慧，设计了一项挑战：在塔的地下迷宫中，隐藏着许多神秘的魔法符文。这些符文是由一群魔法战士在过去留下的，每个符文都有一个与其对应的力量值。老魔法师告诉学徒们，只有当你们发现了符文阵列中的“弱点”时，才算是通过了挑战。

具体来说，老魔法师的“弱点”是指在符文阵列中，存在一些符文的力量值呈现严格递减的顺序。即对于某些位置 $i < j < k$，若符文的力量值满足 $a_i > a_j > a_k$，那么这就是一个“弱点”。

你的任务是帮助学徒们计算出符文阵列中的“弱点”数量，只有掌握了足够的“弱点”才能通过试炼，获得老魔法师的认可。

输入

第一行输入一个整数 $n$ (3 $≤$ $n$ $≤$ $10^6$) — 代表魔法符文的数量。

第二行输入 $n$ 个不同的正整数 $a_1, a_2, ..., a_n$，表示每个符文的力量值，其中 $1 ≤ a_i ≤ 10^9$。

输出

输出一个整数，表示符文阵列中的弱点数，也就是有多少组满足 $i < j < k$ 且 $a_i > a_j > a_k$ 的三元组。

示例

3
3 2 1

1

3
2 3 1

0

4
10 8 3 1

4

4
1 5 4 3

1