题目描述

After returning from the army, Makes received a gift—an array $a$ consisting of $n$ positive integer numbers. He hadn't been solving problems for a long time, so he became interested in answering a particular question: how many triples of indices $(i, j, k)$ ($i < j < k$), such that $a_i \cdot a_j \cdot a_k$ is the minimum possible, are there in the array? Help him with it!

中文题意

给定序列$a_i$，求有多少个三元组$(i, j,k)$满足$i<j<k$且$a_ia_ja_k$是所有三个元素的乘积之中最小的。

数据范围：$3≤n≤10^5,1≤a_i ≤10^9$

#输入

The first line of input contains a positive integer $n$ ($3 \leq n \leq 10^5$) — the number of elements in array $a$. The second line contains $n$ positive integer numbers $a_i$ ($1 \leq a_i \leq 10^9$) — the elements of the given array.

#输出

Print one number — the quantity of triples $(i, j, k)$ such that $i$, $j$, and $k$ are pairwise distinct and $a_i \cdot a_j \cdot a_k$ is the minimum possible.

样例

4
1 1 1 1

4

提示

In the first example, Makes always chooses three ones out of four, and the number of ways to choose them is 4.

5
1 3 2 3 4

2

提示

In the second example, a triple of numbers (1, 2, 3) is chosen (numbers, not indices). Since there are two ways to choose an element 3, then the answer is 2.

6
1 3 3 1 3 2

1

提示

In the third example, a triple of numbers (1, 1, 2) is chosen, and there's only one way to choose indices.