Makes And The Product

2024-01-13 19:18

文章标签 product makes

本文主要是介绍Makes And The Product，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

After returning from the army Makes received a gift — an array a consisting of npositive 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 ≤ 10⁵) — the number of elements in array a. The second line contains n positive integer numbers a_i (1 ≤ a_i ≤ 10⁹) — 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.

Example

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.

有三种情况:

1.最小数字的个数n1>=3,则只需计算

2.n1<3,第二小的数字个数n2>=3-n1,则只需计算

3.n1,n2<3,第三小的数字个数n3>=3-n2-n1,则只需计算

注意结果会超过int

#include<iostream>
#include<queue>
#include<map>
using namespace std;
struct list
{int num,amount;list() {	}list(int a,int b):num(a),amount(b) {	}friend bool operator < (struct list c,struct list d){return c.num>d.num;} 
};
long long C(int a,int b)
{if(b>a-b)b=a-b;if(b==0)return 1;long long up=1,down=1;int i=b;while(i--)up*=a--;for(i=1;i<=b;i++)down*=i;return up/down; 
}
int main()
{int n;while(cin >> n){map<int,int> mp;priority_queue<list> q;while(n--){int a;cin >> a;mp[a]++;}map<int,int>::iterator it;for(it=mp.begin();it!=mp.end();it++)q.push(list(it->first,it->second));if(q.top().amount>=3){cout << C(q.top().amount,3) << endl;continue;}else{int num=q.top().amount;q.pop();if(q.top().amount>=3-num){cout << C(q.top().amount,3-num) << endl;continue;}else{num+=q.top().amount;q.pop();cout << C(q.top().amount,3-num) << endl;}}}return 0;
}

这篇关于Makes And The Product的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！