817B.md (1590B)
1 Source: https://codeforces.com/problemset/problem/817/B 2 3 B. Makes And The Product 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 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! 22 23 Input 24 25 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. 26 27 Output 28 29 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. 30 31 Examples 32 33 Input 34 35 ``` 36 4 37 1 1 1 1 38 ``` 39 40 Output 41 42 ``` 43 4 44 ``` 45 46 Input 47 48 ``` 49 5 50 1 3 2 3 4 51 ``` 52 53 Output 54 55 ``` 56 2 57 ``` 58 59 Input 60 61 ``` 62 6 63 1 3 3 1 3 2 64 ``` 65 66 Output 67 68 ``` 69 1 70 ``` 71 72 Note 73 74 In the first example Makes always chooses three ones out of four, and the number of ways to choose them is 4. 75 76 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. 77 78 In the third example a triple of numbers (1, 1, 2) is chosen, and there's only one way to choose indices.