← 返回题目列表

Codeforces · 61/E

E. 敌人很弱

中文机器翻译题面 查看原题

罗马人再次进攻。这次他们比波斯人强大得多,但沙普尔已准备好击败他们。他说:“一头狮子永远不会害怕一百只羊”。

然而,沙普尔必须找到罗马军队的弱点才能击败他们。所以他给了军队一个弱点数字。

在沙普尔看来,军队的弱点等于三元组 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