从部队回来后,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),并且只有一种方法来选择索引。