Educational Codeforces Round 23 B. Makes And The Product-蒲公英云

Educational Codeforces Round 23 B. Makes And The Product

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;
}