← 返回题目列表

Codeforces · 817/B

B. 品牌和产品

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

从部队回来后,Makes收到了一份礼物——一个由n个正整数组成的数组a。他已经很长时间没有解决问题了,所以他开始有兴趣回答一个特定的问题:数组中有多少个索引 (i, j, k) (i < j < k) 的三元组,使得 ai·aj·ak 的可能性最小?帮帮他吧!

输入

输入的第一行包含一个正整数 n (3 ≤ n ≤ 105) — 数组 a 中的元素数量。第二行包含 n 个正整数 ai (1 ≤ ai ≤ 109) — 给定数组的元素。

输出

打印一个数字 — 三元组 (i, j, k) 的数量,使得 i、j 和 k 两两不同且 ai·aj·ak 尽可能小。

示例

输入 #1

4
1 1 1 1

输出 #1

4

输入 #2

5
1 3 2 3 4

输出 #2

2

输入 #3

6
1 3 3 1 3 2

输出 #3

1

注意

在第一个示例中,Makes 总是从四个中选择三个,选择它们的方式数量为 4。

在第二个示例中,选择了三个数字 (1, 2, 3)(数字,而不是索引)。由于有两种方法选择元素3,所以答案是2。

在第三个示例中,选择了三个数字 (1, 1, 2),并且只有一种方法来选择索引。