Makes And The Product CodeForces - 817B （思维+构造）

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 ai·aj·akis 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 npositive integer numbers ai (1 ≤ ai ≤ 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 ai·aj·ak is minimum possible.

Examples

input

Copy

4
1 1 1 1

output

Copy

input

Copy

5
1 3 2 3 4

output

Copy

input

Copy

6
1 3 3 1 3 2

output

Copy

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.

思路：

分三种情况来逐一考虑，

a[1]=a[2]=a[3]

a[1],a[2]=a[3]

a[1],a[2],a[3]

根据题目要求的约数，只可能为这三种情况，

分类处理下就OK

细节见代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <vector>
#define sz(a) int(a.size())
#define all(a) a.begin(), a.end()
#define rep(i,x,n) for(int i=x;i<n;i++)
#define repd(i,x,n) for(int i=x;i<=n;i++)
#define pii pair<int,int>
#define pll pair<long long ,long long>
#define gbtb ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define MS0(X) memset((X), 0, sizeof((X)))
#define MSC0(X) memset((X), '\0', sizeof((X)))
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define eps 1e-6
#define gg(x) getInt(&x)
#define db(x) cout<<"== [ "<<x<<" ] =="<<endl;
using namespace std;
typedef long long ll;
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}
ll powmod(ll a,ll b,ll MOD){ll ans=1;while(b){if(b%2)ans=ans*a%MOD;a=a*a%MOD;b/=2;}return ans;}
inline void getInt(int* p);
const int maxn=1000010;
const int inf=0x3f3f3f3f;
/*** TEMPLATE CODE * * STARTS HERE ***/
map<ll,ll> m;
ll n;
ll a[maxn];
ll getpc(ll m,ll n)//m 中 选 n 个
{
    long long ans=1;
    for(long long k=1; k<=n; k++)
    {
        ans=(ans*(m-n+k))/k;
    }
    return ans;
}
int main()
{
    gbtb;
    cin>>n;
    repd(i,1,n)
    {
        cin>>a[i];
        m[a[i]]=m[a[i]]+1;
    }
    sort(a+1,a+1+n);
    ll ans=0ll;
    set<ll> s;
    repd(i,1,3)
    {
        s.insert(a[i]);
    }
    // 1 1 1 1 1
    
    if(s.size()==1)
    {
        ll sum=m[a[1]];
        // c 4 3 
        ans=getpc(sum,3);

    }else if(s.size()==2)
    {
        // 1 1 2 2 2 2 3
        // 1 2 2 2 2 2
        ll f=m[a[1]];
        if(f==1)
        {
            ans=getpc(m[a[2]],2);
        }else
        {
            ans=m[a[3]];
        }
    }else 
    {
        // 1 2 3 3 3 3
        ans=m[a[3]];
    }
    // cout<
    cout<<ans<<endl;
    return 0;
}

inline void getInt(int* p) {
    char ch;
    do {
        ch = getchar();
    } while (ch == ' ' || ch == '\n');
    if (ch == '-') {
        *p = -(getchar() - '0');
        while ((ch = getchar()) >= '0' && ch <= '9') {
            *p = *p * 10 - ch + '0';
        }
    }
    else {
        *p = ch - '0';
        while ((ch = getchar()) >= '0' && ch <= '9') {
            *p = *p * 10 + ch - '0';
        }
    }
}