Educational Codeforces Round 23 B. Makes And The Product

雨点打透心脏的1/2处 2022-06-14 09:53 139阅读 0赞

[B. Makes And The Product][]

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

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.

Examples

input

4
    1 1 1 1

output

input

5
    1 3 2 3 4

output

input

6
    1 3 3 1 3 2

output

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.

题目意思：

就是给定N个数，然后按大小顺序排序后，找前三个数，问有多少种不同的组合。

如果是 6

1 1 2 2 3 3

的话前三个数，是1,1,2然后2有两个可以替换，所以是2种情况。以此类推

如果都是一个数的话，那么就是排列组合。

要用LLD才行

#include<bits/stdc++.h>
    #include<iostream>
    using namespace std;
    int number[100005];
    int main()
    {
        int n;
        long long int all = 1;
        scanf("%d",&n);
        for(int i = 0; i < n; i++)
        {
            scanf("%d",&number[i]);
        }
        sort(number,number+n);
        int count = 1,index = 1;
        while(number[index] == number[0] && index < n)
        {
            index++;
            count++;
        }
        if(count >= 3)
        {
            all=all*index;
            all=all*(index-1);
            all=all*(index-2);
            all=all/6;
        }
        else if(count == 2)
        {
            for(int i = 3; i < n; i++)
                if(number[i] == number[2])
                    all++;
        }
        else
        {
            int k = 3;
            while(k<n&&(number[k]==number[2]))
                k++;
            k--;
            if(number[1] == number[2])
            {
                all=k;
                all=all*(k-1);
                all=all/2;
            }
            else
            {
                all=all+(k-2);
            }
        }
        printf("%lld\n",all);
        return 0;
    }

[B. Makes And The Product]: http://codeforces.com/contest/817/problem/B