Question
Number of Ways to Select 3 Students
You are given the marks of n students. Your task is to determine the number of ways to select three different students who have exactly the same marks. Two students are considered different if they have different indices. The order of selection does not matter that means we are forming combinations, not permutations.
Input
The first line contains a single integer n — the number of students.
The second line contains n space-separated, where the i-th integer represents the marks of the i-th student.
The second line contains n space-separated, where the i-th integer represents the marks of the i-th student.
Output
Print a single integer — the number of valid ways to choose three students with the same marks.
Example
Input:
6
10 20 10 30 10 20
Output:
1
Explanation:
There are three students with marks equal to 10.
Only one way exists to choose 3 students out of these 3:
C(3, 3) = 1.
Input:
11
10 20 10 10 20 30 30 20 20 10 30
Output:
9
Explanation:
Marks 10 → 4 students → C(4, 3) = 4 ways
Marks 20 → 4 students → C(4, 3) = 4 ways
Marks 30 → 3 students → C(3, 3) = 1 way
Total ways = 4 + 4 + 1 = 9
6
10 20 10 30 10 20
Output:
1
Explanation:
There are three students with marks equal to 10.
Only one way exists to choose 3 students out of these 3:
C(3, 3) = 1.
Input:
11
10 20 10 10 20 30 30 20 20 10 30
Output:
9
Explanation:
Marks 10 → 4 students → C(4, 3) = 4 ways
Marks 20 → 4 students → C(4, 3) = 4 ways
Marks 30 → 3 students → C(3, 3) = 1 way
Total ways = 4 + 4 + 1 = 9