English · Original
Chinese · Translation
Formal · Original
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 to answer a particular question: how many triples of indices (_i_, _j_, _k_) (_i_ < _j_ < _k_), such that _a__i_·_a__j_·_a__k_ is minimum possible, are there in the array? Help him with it!
## Input
The first line of input contains a positive integer number _n_ (3 ≤ _n_ ≤ 105) — the number of elements in array _a_. The second line contains _n_ positive integer numbers _a__i_ (1 ≤ _a__i_ ≤ 109) — the elements of a given array.
## Output
Print one number — the quantity of triples (_i_, _j_, _k_) such that _i_, _j_ and _k_ are pairwise distinct and _a__i_·_a__j_·_a__k_ is minimum possible.
[samples]
## Note
In the first example Makes always chooses three ones out of four, and the number of ways to choose them is 4.
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.
In the third example a triple of numbers (1, 1, 2) is chosen, and there's only one way to choose indices.
[{"iden":"statement","content":"在从军队归来后，Makes 收到一份礼物——一个由 #cf_span[n] 个正整数组成的数组 #cf_span[a]。由于长时间没有解题，他开始对一个问题产生兴趣：有多少个三元组索引 #cf_span[(i, j, k)]（#cf_span[i < j < k]），使得 #cf_span[ai·aj·ak] 达到最小可能值？请帮助他解决这个问题！\n\n输入的第一行包含一个正整数 #cf_span[n (3 ≤ n ≤ 105)] —— 数组 #cf_span[a] 中的元素个数。第二行包含 #cf_span[n] 个正整数 #cf_span[ai (1 ≤ ai ≤ 109)] —— 给定数组的元素。\n\n输出一个数字——满足 #cf_span[i, j] 和 #cf_span[k] 互不相同且 #cf_span[ai·aj·ak] 达到最小可能值的三元组 #cf_span[(i, j, k)] 的数量。\n\n在第一个例子中，Makes 总是从四个 1 中选出三个，选择它们的方式数为 #cf_span[4]。\n\n在第二个例子中，选择的三元组是数字 #cf_span[(1, 2, 3)]（指数字，而非索引）。由于有两种方式选择元素 #cf_span[3]，因此答案为 #cf_span[2]。\n\n在第三个例子中，选择的三元组是数字 #cf_span[(1, 1, 2)]，且只有一种方式选择索引。"}},{"iden":"input","content":"输入的第一行包含一个正整数 #cf_span[n (3 ≤ n ≤ 105)] —— 数组 #cf_span[a] 中的元素个数。第二行包含 #cf_span[n] 个正整数 #cf_span[ai (1 ≤ ai ≤ 109)] —— 给定数组的元素。"},{"iden":"output","content":"输出一个数字——满足 #cf_span[i, j] 和 #cf_span[k] 互不相同且 #cf_span[ai·aj·ak] 达到最小可能值的三元组 #cf_span[(i, j, k)] 的数量。"},{"iden":"examples","content":"输入41 1 1 1输出4输入51 3 2 3 4输出2输入61 3 3 1 3 2输出1"},{"iden":"note","content":"在第一个例子中，Makes 总是从四个 1 中选出三个，选择它们的方式数为 #cf_span[4]。在第二个例子中，选择的三元组是数字 #cf_span[(1, 2, 3)]（指数字，而非索引）。由于有两种方式选择元素 #cf_span[3]，因此答案为 #cf_span[2]。在第三个例子中，选择的三元组是数字 #cf_span[(1, 1, 2)]，且只有一种方式选择索引。"}]
**Definitions**
Let $ n \in \mathbb{Z} $ with $ 3 \leq n \leq 10^5 $.
Let $ A = (a_1, a_2, \dots, a_n) $ be a sequence of positive integers with $ 1 \leq a_i \leq 10^9 $.
Let $ T = \{ (i,j,k) \in \{1,\dots,n\}^3 \mid i < j < k \} $ be the set of all valid index triples.
**Constraints**
1. $ n \geq 3 $
2. $ a_i \geq 1 $ for all $ i \in \{1, \dots, n\} $
**Objective**
Let $ m = \min \{ a_i \cdot a_j \cdot a_k \mid (i,j,k) \in T \} $.
Compute the number of triples $ (i,j,k) \in T $ such that $ a_i \cdot a_j \cdot a_k = m $.
API Response (JSON)
{
"problem": {
"name": "B. Makes And The Product",
"description": {
"content": "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 to answer a part",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 2000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF817B"
},
"statements": [
{
"statement_type": "Markdown",
"content": "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 to answer a part...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "[{\"iden\":\"statement\",\"content\":\"在从军队归来后，Makes 收到一份礼物——一个由 #cf_span[n] 个正整数组成的数组 #cf_span[a]。由于长时间没有解题，他开始对一个问题产生兴趣：有多少个三元组索引 #cf_span[(i, j, k)]（#cf_span[i < j < k]），使得 #cf_span[ai·aj·ak] 达到最小可能值？请帮...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ n \\in \\mathbb{Z} $ with $ 3 \\leq n \\leq 10^5 $. \nLet $ A = (a_1, a_2, \\dots, a_n) $ be a sequence of positive integers with $ 1 \\leq a_i \\leq 10^9 $.\n\nLet $ T = \\{ (i,j,k) \\in...",
"is_translate": false,
"language": "Formal"
}
]
}