罗马人再次进攻。这次他们比波斯人强大得多,但沙普尔已准备好击败他们。他说:“一头狮子永远不会害怕一百只羊”。
然而,沙普尔必须找到罗马军队的弱点才能击败他们。所以他给了军队一个弱点数字。
在沙普尔看来,军队的弱点等于三元组 i、j、k 的数量,使得 i < j < k 且 ai > aj > ak,其中 ax 是站在位置 x 的人的力量。罗马军队有一个特点——军队中所有人的权力都是不同的。
帮助沙普尔找出罗马人有多弱。
输入
输入的第一行包含一个数字 n (3 ≤ n ≤ 106) — 罗马军队的人数。下一行包含 n 个不同的正整数 ai (1 ≤ i ≤ n, 1 ≤ ai ≤ 109) — 罗马军队中士兵的权力。
输出
单个整数,罗马军队的弱点。
请不要使用 %lld 说明符在 C++ 中读取或写入 64 位整数。最好使用 cout (也可以使用 %I64d)。
示例
输入 #1
3 3 2 1
输出 #1
1
输入 #2
3 2 3 1
输出 #2
0
输入 #3
4 10 8 3 1
输出 #3
4
输入#4
4 1 5 4 3
输出#4
1