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 ≤ 10^5) — the number of elements in array a. The second line contains n positive integer numbers a_{i} (1 ≤ a_{i} ≤ 10^9) — 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
4

Input
5
1 3 2 3 4

Output
2

Input
6
1 3 3 1 3 2

Output
1



-----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.

Source: codeforces | Difficulty: MEDIUM
Tags: Mathematics

Sorting

Combinatorics

Implementation


Solutions:
import sys, os
from io import BytesIO, IOBase
import collections, itertools, bisect, heapq, math, string
from decimal import *
BUFSIZE = 8192
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def main():
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	x = set()
	for i in range(3):
		x.add(a[i])
	s = list(x)
	if len(s) == 3:
		print(a.count(s[2]))
	elif len(s) == 1:
		tmp = a.count(s[0])
		print(tmp * (tmp - 1) * (tmp - 2) // 6)
	elif a.count(a[0]) == 2:
		tmp = a.count(s[0])
		print(tmp * (tmp - 1) // 2 * a.count(s[1]))
	else:
		tmp = a.count(s[1])
		print(tmp * (tmp - 1) // 2)
main()


n = int(input())
ai = list(map(int, input().split()))
ai.sort()
i = ai[0]
j = ai[1]
k = ai[2]
ans = 0
for num in range(2, n):
	if k == ai[num]:
		ans += 1
if j == k:
	if i == j:
		num2 = ans
		ans = 0
		for num in range(1, num2 + 2):
			ans += num * (num - 1) // 2
	else:
		ans = ans * (ans + 1) // 2
print(ans)


n = int(input())
a = [int(x) for x in input().split()]
a.sort()
l = [a[0], a[1], a[2]]
mx = 0
val = l.count(l[0])
val2 = l.count(l[1])
val3 = l.count(l[2])
if val == 2:
	val = a.count(l[2])
	mx = max(mx, val)
elif val == 3:
	val = a.count(l[0])
	val = val * (val - 1) * (val - 2) // 6
	mx = max(mx, val)
elif val2 == 2:
	val = a.count(l[1])
	val = val * (val - 1) // 2
	mx = max(mx, val)
else:
	for i in l:
		mx = max(mx, a.count(i))
print(mx)


import sys
from bisect import bisect_right as lb
from collections import deque
from queue import PriorityQueue as pq
from math import *
input_ = lambda : sys.stdin.readline().strip('\r\n')
ii = lambda : int(input_())
il = lambda : list(map(int, input_().split()))
ilf = lambda : list(map(float, input_().split()))
ip = lambda : input_()
fi = lambda : float(input_())
ap = lambda ab, bc, cd: ab[bc].append(cd)
li = lambda : list(input_())
pr = lambda x: print(x)
prinT = lambda x: print(x)
f = lambda : sys.stdout.flush()
inv = lambda x: pow(x, mod - 2, mod)
mod = 10 ** 9 + 7

def comb(x, y):
	if y == 3:
		return x * (x - 1) * (x - 2) // 6
	elif y == 2:
		return x * (x - 1) // 2
	else:
		return x
n = ii()
a = il()
b = sorted(a)
c = b[:3]
ans = 1
d = {}
for i in c:
	if not d.get(i):
		ans *= comb(a.count(i), c.count(i))
		d[i] = 1
print(ans)


import sys
from collections import Counter
n = int(input())
cnt = Counter(map(int, input().split()))
x = 3
ans = 1
for k in sorted(cnt.keys()):
	if min(cnt[k], x) == 3:
		ans *= cnt[k] * (cnt[k] - 1) * (cnt[k] - 2) // 6
		x -= 3
	elif min(cnt[k], x) == 2:
		ans *= cnt[k] * (cnt[k] - 1) // 2
		x -= 2
	else:
		ans *= cnt[k]
		x -= 1
	if x == 0:
		break
print(ans)


n = int(input())
l = list(map(int, input().split()))
l.sort()
a = l[0]
b = l[1]
c = l[2]
if a < b < c:
	print(l.count(c))
elif a < b and b == c:
	x = l.count(b)
	print(x * (x - 1) // 2)
elif a == b and b < c:
	print(l.count(c))
else:
	x = l.count(a)
	print(x * (x - 1) * (x - 2) // 6)


n = int(input())
a = list(map(int, input().split()))
a.sort()
k = a.count(a[2])
if a[1] < a[2]:
	print(k)
elif a[0] < a[1]:
	print(k * (k - 1) // 2)
else:
	print(k * (k - 1) * (k - 2) // 6)


n = int(input())
l = list(map(int, input().strip().split(' ')))
l1 = sorted(l)
a = l1[0]
b = l1[1]
c = l1[2]
if a == b and b == c:
	ans = l.count(a)
	a = ans
	print(a * (a - 1) * (a - 2) // 6)
elif b != c:
	ans = l.count(c)
	c = ans
	print(c)
else:
	ans = l.count(b)
	b = ans
	print(b * (b - 1) // 2)


import os
n = int(input())
arr = [int(x) for x in input().strip().split()]
arr.sort()
count = 0
firstindex = -1
for i in range(0, n):
	if arr[i] == arr[2]:
		if firstindex == -1:
			firstindex = i
		count = count + 1
	elif arr[i] > arr[2]:
		break
	else:
		continue
choosenum = 2 - firstindex + 1
result = 1
tmp = 1
for i in range(0, choosenum):
	result *= count - i
	tmp *= choosenum - i
print(int(result / tmp))


import sys
l = int(input())
arr = list(map(int, input().split()))
arr.sort()
if arr[0] != arr[1] and arr[1] != arr[2] or (arr[0] == arr[1] and arr[1] != arr[2]):
	print(arr.count(arr[2]))
elif arr[0] != arr[1] and arr[1] == arr[2]:
	n = arr.count(arr[1])
	print(int(n * (n - 1) / 2))
elif arr[0] == arr[1] == arr[2]:
	n = arr.count(arr[0])
	print(int(n * (n - 1) * (n - 2) / 6))


n = int(input())
inp = input().split()
l = []
for val in inp:
	l.append(int(val))
l.sort()
count = 3
while count < n and l[count] == l[count - 1]:
	count += 1
if l[2] != l[1]:
	print(count - 2)
elif l[2] != l[0]:
	print((count - 1) * (count - 2) // 2)
else:
	print(count * (count - 1) * (count - 2) // 6)


n = int(input())
l = list(map(int, input().split()))
l.sort()
(x, y, z) = (l.count(l[0]), l.count(l[1]), l.count(l[2]))
if x > 2:
	print(x * (x - 1) * (x - 2) // 6)
elif x == 1 and y >= 2:
	print(y * (y - 1) // 2)
else:
	print(z)


from collections import Counter
n = int(input())
a = list(map(int, input().split()))
a.sort()
b = list(set(a))
b.sort()
c = Counter(a)
if c[b[0]] >= 3:
	k = c[b[0]]
	print(int(k * (k - 1) * (k - 2) / 6))
else:
	k = c[b[0]]
	if len(b) == 1:
		j = 0
	else:
		j = c[b[1]]
	if k == 2:
		print(j)
	elif k == 1:
		if j >= 3:
			print(int(j * (j - 1) / 2))
		elif j == 2:
			print(1)
		elif len(b) <= 2:
			print(0)
		else:
			print(c[b[2]])


def main():
	n = map(int, input().split())
	a = list(map(int, input().split()))
	a.sort()
	if a[0] <= a[1] < a[2]:
		ans = a.count(a[2])
	elif a[0] < a[1] == a[2]:
		ans = a.count(a[2])
		ans = ans * (ans - 1) // 2
	elif a[0] == a[1] == a[2]:
		ans = a.count(a[2])
		ans = ans * (ans - 1) * (ans - 2) // 6
	print(ans)
main()


n = int(input())
a = list(map(int, input().split()))
a1 = sorted(a)
(k1, k2, k3) = (a1[0], a1[1], a1[2])
pre = [0, 0, 0]
ans = 0
for i in range(n):
	if a[i] == k1:
		pre[0] += 1
	if a[i] == k2:
		pre[1] += 1
	if a[i] == k3:
		pre[2] += 1
if k1 != k2 and k1 != k3 and (k3 != k2):
	ans = pre[0] * pre[1] * pre[2]
if k1 == k2:
	ans = pre[0] * (pre[0] - 1) // 2 * pre[2]
if k2 == k3:
	ans = pre[0] * (pre[1] * (pre[1] - 1) // 2)
if k1 == k2 and k2 == k3:
	ans = pre[0] * (pre[0] - 1) * (pre[0] - 2) // 6
print(ans)


import math

def newton(n, k):
	if k == n:
		return 1
	if k == 1:
		return n
	if k > n:
		return 0
	a = math.factorial(n)
	b = math.factorial(k)
	c = math.factorial(n - k)
	return a // (b * c)
n = int(input())
S = dict()
L = sorted(list(map(int, input().split())))
for e in L:
	if e in S:
		S[e] += 1
	else:
		S[e] = 1
L = sorted(set(L))
cnt = 0
cnt2 = 0
for e in L:
	cnt += S[e]
	if cnt >= 3:
		print(newton(S[e], S[e] - (3 - cnt2)))
		break
	cnt2 += S[e]


num = int(input())
arr = [0] * num
arr = input().split()
for i in range(num):
	arr[i] = int(arr[i])
arr.sort()
a = arr[0]
b = arr[1]
c = arr[2]
ans = 1
ca = arr.count(a)
cb = arr.count(b)
cc = arr.count(c)
if c != b and b != a:
	ans = ca * cb * cc
elif b == c and b != a:
	ans = ca * (cb * (cb - 1) // 2)
elif a == b and b != c:
	ans = ca * (ca - 1) // 2 * cc
elif a == b and b == c:
	ans = ca * (ca - 1) * (ca - 2) // 6
print(ans)


import math

def arrange(n, k):
	return int(math.factorial(n) / (math.factorial(k) * math.factorial(n - k)))
total_number = int(input())
data = list(map(int, input().split()))
data_sorted = sorted(data)
answer = 1
for i in list(set(data_sorted[:3])):
	n = data.count(i)
	k = data_sorted[:3].count(i)
	answer *= arrange(n, k)
print(answer)


def C(n, r):
	if r > n // 2:
		r = n - r
	ans = 1
	for i in range(1, r + 1):
		ans *= n - r + i
		ans //= i
	return ans
n = input()
a = list(map(int, input().split()))
a.sort()
b = set(a[0:3])
m = {}
for i in b:
	m[i] = 0
for i in a[0:3]:
	m[i] += 1
ans = 1
for i in m:
	ans *= C(a.count(i), m[i])
print(ans)


n = input()
a = [int(n) for n in input().split()]
a.sort()
first = a.count(a[0])
second = a.count(a[1])
if a[0] == a[1]:
	second -= 1
third = a.count(a[2])
if first >= 3:
	ans = first * (first - 1) * (first - 2) / 6
elif second >= 2:
	ans = second * (second - 1) / 2
else:
	ans = third
print(int(ans))


import sys
from math import *

def minp():
	return sys.stdin.readline().strip()

def mint():
	return int(minp())

def mints():
	return map(int, minp().split())

def fact(x):
	r = 1
	for i in range(1, x + 1):
		r *= i
	return r
n = mint()
a = list(mints())
a.sort()
i = 0
z = []
while i < n:
	j = i
	while j < n and a[j] == a[i]:
		j += 1
	z.append(j - i)
	if len(z) > 3:
		break
	i = j
if z[0] >= 3:
	print(z[0] * (z[0] - 1) * (z[0] - 2) // 6)
elif z[0] == 2:
	print(z[1])
elif z[0] == 1 and z[1] >= 2:
	print(z[1] * (z[1] - 1) // 2)
else:
	print(z[2])


import operator as op
from functools import reduce

def comb(n, r):
	r = min(r, n - r)
	if r == 0:
		return 1
	numer = reduce(op.mul, range(n, n - r, -1))
	denom = reduce(op.mul, range(1, r + 1))
	return numer // denom
n = int(input())
l = [int(i) for i in input().split()]
d = sorted(l)
a = d[0]
b = d[1]
c = d[2]
if a == b and b == c:
	print(comb(l.count(a), 3))
elif a == b:
	print(l.count(c))
elif b == c:
	print(comb(l.count(c), 2))
else:
	print(l.count(c))


n = int(input())
l = list(map(int, input().split()))
l = sorted(l)
(x, y, z) = (l[0], l[1], l[2])
if x < y < z:
	print(l.count(z))
if x < y and y == z:
	c = l.count(y)
	print(c * (c - 1) // 2)
if x == y and y < z:
	print(l.count(z))
if x == y and y == z:
	c = l.count(x)
	ans = c * (c - 1) * (c - 2)
	print(ans // 6)


n = int(input())
lis = list(map(int, input().split()))
min = 10 ** 9
a = 0
for i in lis:
	if min == i:
		a += 1
	elif min > i:
		a = 1
		min = i
if a >= 3:
	print(a * (a - 1) * (a - 2) // 6)
else:
	b = a
	min1 = min
	min = 10 ** 9
	for i in lis:
		if min == i:
			a += 1
		elif min > i and i != min1:
			min = i
			a = 1
	if a + b >= 3:
		if b == 2:
			print(a)
		else:
			print(a * (a - 1) // 2)
	else:
		c = b
		b = a
		min2 = min
		min = 10 ** 9
		for i in lis:
			if min == i:
				a += 1
			elif min > i and i != min1 and (i != min2):
				min = i
				a = 1
		print(a)


def c(n, k):
	r = 1
	for i in range(k):
		r *= n
		n -= 1
	for i in range(2, k + 1):
		r //= i
	return r
n = int(input())
l = sorted(map(int, input().split()))
prev = l[0]
beg = 0
cnt = 0
ans = 1
for i in range(n):
	if l[i] == prev:
		cnt += 1
	else:
		ans *= c(i - beg, min(3, i) - beg)
		cnt = 1
		prev = l[i]
		beg = i
		if i > 2:
			break
if beg < 3:
	ans *= c(n - beg, 3 - beg)
print(ans)


n = int(input())
a = list(map(int, input().split()))
a.sort()
if a[2] != a[1]:
	print(a.count(a[2]))
elif a[2] != a[0]:
	c = a.count(a[2])
	print(int(c * (c - 1) / 2))
else:
	c = a.count(a[2])
	n = 0
	for i in range(c - 2):
		n += (i + 1) * (i + 2) // 2
	print(n)


from math import factorial
n = int(input())
a = [int(x) for x in input().split()]
web = 3
while web > 0:
	if a.count(min(a)) >= web:
		r = a.count(min(a))
		e = factorial(r)
		f = factorial(web) * factorial(r - web)
		e /= f
		print(int(e))
		exit(0)
	else:
		web -= a.count(min(a))
		e = min(a)
		while e in a:
			a.remove(e)


n = int(input())
a = sorted(map(int, input().split()))
(x, y, z) = (a[0], a[1], a[2])
if x < y < z:
	print(a.count(z))
elif x < y <= z:
	c = a.count(y)
	print(c * (c - 1) // 2)
elif x <= y < z:
	print(a.count(z))
else:
	c = a.count(z)
	print(c * (c - 1) * (c - 2) // 6)


n = int(input())
a = [int(i) for i in input().split()]
a.sort()
same = 1
while same < 3 and a[2 - same] == a[2]:
	same += 1
cnt = 1
i = 3
if same == 1:
	while i < n and a[i] == a[2]:
		cnt += 1
		i += 1
if same == 2:
	while i < n and a[i] == a[2]:
		cnt += same
		same += 1
		i += 1
if same == 3:
	while i < n and a[i] == a[2]:
		cnt += int(same * (same - 1) / 2)
		same += 1
		i += 1
print(cnt)


from math import factorial
n = int(input())
a = [int(i) for i in input().split()]
a.sort()
c1 = c2 = c3 = 0
for i in range(n):
	if a[i] == a[0]:
		c1 += 1
	if a[i] == a[1]:
		c2 += 1
	if a[i] == a[2]:
		c3 += 1
if a[0] == a[1]:
	if a[1] == a[2]:
		print(c1 * (c1 - 1) * (c1 - 2) // 6)
		exit()
	else:
		print(c1 * (c1 - 1) // 2 * c3)
		exit()
if a[1] == a[2]:
	print(c1 * c2 * (c2 - 1) // 2)
	exit()
print(c1 * c2 * c3)


from math import *

def nCr(n, r):
	p = 1
	k = 1
	if n - r < r:
		r = n - r
	if r != 0:
		while r:
			p *= n
			k *= r
			m = gcd(p, k)
			p //= m
			k //= m
			n -= 1
			r -= 1
	else:
		p = 1
	return p
n = int(input())
a = list(map(int, input().split()))
a.sort()
k = a[2]
c = 0
for i in range(3, n):
	if a[i] == k:
		c += 1
	else:
		break
if a[0] == a[1] and a[1] == a[2]:
	print(nCr(c + 3, 3))
elif a[0] != a[1] and a[1] == a[2]:
	print(nCr(c + 2, 2))
else:
	print(c + 1)


n = int(input())
raw_array = input().split()
inted = [int(i) for i in raw_array]
x = min(inted)
inted.remove(x)
y = min(inted)
inted.remove(y)
z = min(inted)
inted.remove(z)
inted.append(x)
inted.append(y)
inted.append(z)
if x == y and y == z:
	C = inted.count(x)
	F = C * (C - 1) * (C - 2) / 6
	print(int(F))
elif x == y and y != z:
	C = inted.count(z)
	print(int(C))
elif x != y and y == z:
	C = inted.count(y)
	F = C * (C - 1) / 2
	print(int(F))
elif x != y and y != z:
	C = inted.count(z)
	print(int(C))


n = int(input())
a = list(map(int, input().split(' ')))
a = sorted(a)
a.append(0)
ans = 1
t = 0
while a[3 + t] == a[2]:
	t = t + 1
if a[3] == a[0]:
	ans = (t + 3) * (t + 2) * (t + 1) / 6
elif a[3] == a[1]:
	ans = (t + 2) * (t + 1) / 2
elif a[3] == a[2]:
	ans = t + 1
print(int(ans))


n = int(input())
a = list(map(int, input().split()))
a.sort()
if a[0] != a[1] and a[1] != a[2]:
	print(a.count(a[2]))
elif a[0] != a[1] and a[1] == a[2]:
	temp = a.count(a[2])
	ans = temp * (temp - 1) // 2
	print(ans)
elif a[0] == a[1] and a[1] != a[2]:
	temp = a.count(a[2])
	print(temp)
else:
	temp = a.count(a[2])
	ans = temp * (temp - 1) * (temp - 2) // 6
	print(ans)


from math import factorial as f
from functools import reduce

def C(n, k):
	return f(n) // f(k) // f(n - k)
input()
a = list(map(int, input().split()))
less = sorted(a)[:3]
s = set(less)
m = [less.count(i) for i in s]
n = [a.count(i) for i in s]
print(reduce(lambda x, y: x * y, list(map(lambda x, y: C(x, y), n, m)), 1))


from collections import Counter

def main():
	int(input())
	a = list(map(int, input().split()))
	a.sort()
	(x, y, z) = a[:3]
	freq = Counter(a)
	if x == y and y == z:
		ans = freq[x] * (freq[x] - 1) * (freq[x] - 2) // 6
	elif x == y:
		ans = freq[x] * (freq[x] - 1) * freq[z] // 2
	elif x == z:
		ans = freq[x] * (freq[x] - 1) * freq[y] // 2
	elif y == z:
		ans = freq[y] * (freq[y] - 1) * freq[x] // 2
	else:
		ans = freq[x] * freq[y] * freq[z]
	print(ans)
main()


n = int(input())
l = list(map(int, input().split()))
l.sort()
g = []

def combi(n, r):
	p = 1
	for i in range(min(r, n - r)):
		p = p * (n - i) // (i + 1)
	return p
d = 1
if l[0] == l[1] == l[2]:
	d = d * combi(l.count(l[0]), 3)
elif l[0] != l[1] == l[2]:
	d = d * combi(l.count(l[2]), 2) * l.count(l[0])
elif l[0] == l[1] != l[2]:
	d = d * combi(l.count(l[0]), 2) * l.count(l[2])
elif l[0] != l[1] != l[2]:
	d = d * l.count(l[0]) * l.count(l[1]) * l.count(l[2])
print(d)


from math import factorial as f
input()
a = sorted(input().split(), key=int)
(x, y) = (a.count(a[2]), a[:3].count(a[2]))
print(f(x) // (f(y) * f(x - y)))


n = int(input())
a = [int(i) for i in input().split()]
a.sort()
counter = 0
ch = a[2]
for j in range(n):
	if a[j] == ch:
		counter += 1
	elif counter != 0:
		break
if a[2] != a[1]:
	print(counter)
elif a[1] != a[0]:
	print(int(counter * (counter - 1) / 2))
else:
	c = 0
	for i in range(counter - 1):
		c += i * (i + 1) / 2
	print(int(c))


n = int(input())
l = sorted(list(map(int, input().split())))
ans = 0
if l[2] > l[1]:
	for i in range(2, n):
		if l[i] == l[2]:
			ans += 1
		else:
			break
elif l[1] > l[0]:
	num = 0
	for i in range(1, n):
		if l[i] == l[1]:
			num += 1
		else:
			break
	ans = num * (num - 1) // 2
else:
	num = 0
	for i in range(0, n):
		if l[i] == l[0]:
			num += 1
		else:
			break
	ans = num * (num - 1) * (num - 2) // 6
print(ans)


import atexit, io, sys, collections, math, heapq, fractions, copy, os
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
n = int(input())
ais = list(map(int, input().split()))
ais.sort()
(u, v, w) = ais[:3]
cc = collections.Counter(ais)
if u == v == w:
	q = cc[u]
	print(q * (q - 1) * (q - 2) // 6)
elif u == v and v != w:
	q = cc[w]
	print(q)
elif u != v and v == w:
	q = cc[w]
	print(q * (q - 1) // 2)
elif u != v and v != w:
	q = cc[w]
	print(q)


def list_input():
	return list(map(int, input().split()))
n = int(input())
a = list_input()
a.sort()
s = list()
p = 0
while p < n:
	q = p
	while q < n and a[p] == a[q]:
		q += 1
	s.append(q - p)
	p = q
res = 0
if s[0] >= 3:
	res = s[0] * (s[0] - 1) * (s[0] - 2) // 6
elif s[0] == 2:
	res = s[1]
elif s[0] == 1:
	if s[1] >= 2:
		res = s[1] * (s[1] - 1) // 2
	elif s[1] == 1:
		res = s[2]
print(res)


n = int(input())
a = list(map(int, input().split()))
best = sorted(a)[:3]
leftMin = [(a[0], 1)] + [None] * (n - 1)
for i in range(1, n):
	if a[i] < leftMin[i - 1][0]:
		leftMin[i] = (a[i], 1)
	elif a[i] == leftMin[i - 1][0]:
		leftMin[i] = (a[i], leftMin[i - 1][1] + 1)
	else:
		leftMin[i] = leftMin[i - 1]
rightMin = [None] * (n - 1) + [(a[-1], 1)]
for i in range(n - 2, -1, -1):
	if a[i] < rightMin[i + 1][0]:
		rightMin[i] = (a[i], 1)
	elif a[i] == rightMin[i + 1][0]:
		rightMin[i] = (a[i], rightMin[i + 1][1] + 1)
	else:
		rightMin[i] = rightMin[i + 1]
ret = 0
for i in range(1, n - 1):
	triple = sorted((leftMin[i - 1][0], a[i], rightMin[i + 1][0]))
	if best == triple:
		ret += leftMin[i - 1][1] * rightMin[i + 1][1]
print(ret)


n = int(input())
list = []
for i in input().split(' '):
	list.append(int(i))
list.sort()
(a, b, c) = (list[0], list[1], list[2])
ind = 2
count = 0
while ind < n and list[ind] == c:
	ind += 1
count = ind - 2
if b != c:
	print(count)
elif a != b:
	print(count * (count + 1) // 2)
else:
	print(count * (count + 1) * (count + 2) // 6)


n = int(input())
array = list(map(int, input().rstrip().split()))
array.sort()
i = 3
while i < n and array[i] == array[2]:
	i += 1
else:
	if array[0] == array[1] == array[2]:
		print(i * (i - 1) * (i - 2) // 6)
	elif array[1] == array[2]:
		print((i - 1) * (i - 2) // 2)
	else:
		print(i - 2)


def split1(s):
	l = []
	m = ''
	s += ' '
	for i in range(len(s)):
		if s[i] == ' ':
			l.append(int(m))
			m = ''
		else:
			m += s[i]
	return l
n = int(input())
a = input()
a = split1(a)
aa = a.copy()
z = []
for i in range(3):
	q = min(aa)
	z.append(q)
	aa.remove(q)
t = []
j = 1
for i in z:
	if not i in t:
		if z.count(i) == 1:
			j *= a.count(i)
		if z.count(i) == 2:
			q = a.count(i)
			j *= q * (q - 1) / 2
		if z.count(i) == 3:
			q = a.count(i)
			j *= q * (q - 1) * (q - 2) / 6
	t.append(i)
print(int(j))


n = int(input())
a = list(map(int, input().split()))
a.sort()
fir = a.count(a[0])
sec = a.count(a[1])
th = a.count(a[2])
if a[0] == a[1] and a[1] == a[2]:
	print(fir * (fir - 1) * (fir - 2) // 6)
elif a[0] == a[1]:
	print(fir * (fir - 1) // 2 * th)
elif a[1] == a[2]:
	print(fir * sec * (sec - 1) // 2)
else:
	print(fir * sec * th)


from math import factorial
n = int(input())
a = map(int, input().split())
a = sorted(a)
(x, y) = (a.count(a[2]), a[:3].count(a[2]))
print(factorial(x) // (factorial(x - y) * factorial(y)))


import math

def combinatorics(n, k):
	return int(math.factorial(n) / (math.factorial(n - k) * math.factorial(k)))
n = int(input())
L = list(map(int, input().split()))
K = L[:]
a = min(K)
Ia = K.index(a)
K.remove(a)
b = min(K)
Ib = K.index(b)
K.remove(b)
c = min(K)
Ic = K.index(c)
Ca = L.count(a)
Cb = L.count(b)
Cc = L.count(c)
if a != b:
	if b != c:
		print(Ca * Cb * Cc)
	else:
		print(Ca * combinatorics(Cb, 2))
elif b != c:
	print(combinatorics(Ca, 2) * Cc)
else:
	print(combinatorics(Ca, 3))


from collections import Counter
n = int(input())
A = list(map(int, input().split()))
A.sort()
X = list(set(A))
X = X[:3]
c = Counter(A)
count = 0
mat = []
for x in c.keys():
	count += c[x]
	mat.append(x)
	if count >= 3:
		break
count = 0
res = -1
x = 0
for j in mat:
	x = count
	count += c[j]
	if count > 3:
		res = j
u = c[res]
v = 3 - x
if v == 0 or u == 0:
	print(1)
elif v == 1:
	print(u)
elif v == 2:
	print(u * (u - 1) // 2)
else:
	print(u * (u - 1) * (u - 2) // 6)


R = lambda : list(map(int, input().split()))
n = int(input())
a = list(R())
a.sort()
(x, c) = (a[0], 3)
if n == 3 or a[2] < a[3]:
	print('1')
	return
elif a[1] < a[2]:
	x = a[2]
	c = 1
elif a[0] < a[1]:
	x = a[1]
	c = 2
t = sum((x == y for y in a))
f = 1
for i in range(c):
	f = f * (t - i) / (i + 1)
print(int(f))


n = int(input())
s = input().split()
ar = []
ct = dict()
for i in range(0, n):
	ar.append(int(s[i]))
	if ar[i] in ct:
		ct[ar[i]] += 1
	else:
		ct[ar[i]] = 1
ar.sort()
if ar[0] == ar[1] and ar[0] == ar[2]:
	l = ct[ar[0]]
	k = l * (l - 1) * (l - 2) // (3 * 2 * 1)
elif ar[0] == ar[1]:
	l = ct[ar[0]]
	k = l * (l - 1) // (2 * 1)
	k = k * ct[ar[2]]
elif ar[1] == ar[2]:
	l = ct[ar[1]]
	k = l * (l - 1) // (2 * 1)
	k = k * ct[ar[0]]
else:
	k = ct[ar[0]] * ct[ar[1]] * ct[ar[2]]
print(k)


import math
import sys
temp = sys.stdin.readline()
inp = [int(x) for x in sys.stdin.readline().strip().split(' ')]
inp = sorted(inp)
(a, b, c) = (inp[0], inp[1], inp[2])
counts = dict()
for x in inp:
	if x in counts:
		counts[x] = counts[x] + 1
	else:
		counts[x] = 1
if a == b and b == c:
	n = counts[a]
	r = 3
	if n == 3:
		print(1)
		sys.exit()
	combos = math.factorial(n) // (math.factorial(r) * math.factorial(n - r))
	print(int(combos))
elif a == b and b != c:
	combos = counts[c] * counts[a] * (counts[a] - 1) / 2
	print(int(combos))
elif a != b and b == c:
	combos = counts[a] * counts[b] * (counts[b] - 1) / 2
	print(int(combos))
else:
	combos = counts[a] * counts[b] * counts[c]
	print(combos)


n = int(input())
l = [int(x) for x in input().split()]
l.sort()
(x, y, z) = (l.count(l[0]), l.count(l[1]), l.count(l[2]))
if x > 2:
	print(x * (x - 1) * (x - 2) // 6)
elif x == 1 and y >= 2:
	print(y * (y - 1) // 2)
else:
	print(z)


n = int(input())
a = sorted(list(map(int, input().split())))
min1 = a[0]
min2 = a[1]
min3 = a[2]
t = True
if min1 == min2 and min2 == min3:
	cnt = 0
	for i in a:
		if i == min1:
			cnt += 1
	cnt = cnt * (cnt - 1) * (cnt - 2)
	print(cnt // 6)
	t = False
if min1 == min2 and t:
	cnt12 = 0
	cnt3 = 0
	for i in a:
		if i == min1:
			cnt12 += 1
		if i == min3:
			cnt3 += 1
	print(cnt12 * (cnt12 - 1) // 2 * cnt3)
if min1 == min3 and t:
	cnt13 = 0
	cnt2 = 0
	for i in a:
		if i == min1:
			cnt13 += 1
		if i == min2:
			cnt2 += 1
	print(cnt13 * (cnt13 - 1) // 2 * cnt2)
if min3 == min2 and t:
	cnt32 = 0
	cnt1 = 0
	for i in a:
		if i == min3:
			cnt32 += 1
		if i == min1:
			cnt1 += 1
	print(cnt32 * (cnt32 - 1) // 2 * cnt1)
if min1 != min2 and min2 != min3 and (min1 != min3):
	cnt1 = 0
	cnt2 = 0
	cnt3 = 0
	for i in a:
		if i == min1:
			cnt1 += 1
		if i == min2:
			cnt2 += 1
		if i == min3:
			cnt3 += 1
	print(cnt1 * cnt2 * cnt3)


n = int(input())
l = [int(i) for i in input().split()]
from collections import Counter
c = Counter(l)
l = set(l)
l = list(l)
l.sort()
from math import factorial as f

def nck(n, r):
	return f(n) // (f(r) * f(n - r))
curr = 0
k = 3
for i in l:
	if curr + c[i] <= k:
		curr += c[i]
		if curr == k:
			print(1)
			break
	else:
		rem = k - curr
		print(nck(c[i], rem))
		break


def main():

	def findout(A):
		MIN = 10 ** 9 + 1
		for i in range(len(A)):
			if A[i] < MIN:
				MIN = A[i]
		count1 = 0
		for i in range(len(A)):
			if A[i] == MIN:
				count1 += 1
		MIN2 = 10 ** 9 + 1
		for i in range(len(A)):
			if A[i] > MIN and A[i] < MIN2:
				MIN2 = A[i]
		count2 = 0
		for i in range(len(A)):
			if A[i] == MIN2:
				count2 += 1
		x = count1
		if count2 == 0 or count1 >= 3:
			return x * (x - 1) * (x - 2) // 6
		if count1 == 2:
			return count2
		if count1 == 1 and count2 >= 2:
			return count2 * (count2 - 1) // 2
		MIN3 = 10 ** 9 + 1
		for i in range(len(A)):
			if A[i] > MIN2 and A[i] < MIN3:
				MIN3 = A[i]
		count3 = 0
		for i in range(len(A)):
			if A[i] == MIN3:
				count3 += 1
		return count3
	N = int(input())
	A = list(map(int, input().strip().split(' ')))
	print(findout(A))
main()


def cal_combine_count(x, y):
	if y == 1:
		return x
	elif y == 2:
		return int(x * (x - 1) / 2)
	elif y == 3:
		return int(x * (x - 1) * (x - 2) / 6)
n = int(input())
input_str = input()
arr = list([int(a) for a in input_str.split()])
arr.sort()
min_tri = list(set(arr[0:3]))
min_tri.sort()
if len(min_tri) == 1:
	x = arr.count(min_tri[0])
	print(cal_combine_count(x, 3))
elif len(min_tri) == 2:
	x1 = arr[0:3].count(min_tri[0])
	x2 = arr.count(min_tri[1])
	if x1 == 1:
		print(cal_combine_count(x2, 2))
	else:
		print(cal_combine_count(x2, 1))
else:
	x = arr.count(min_tri[2])
	print(cal_combine_count(x, 1))


n = int(input())
a = list(map(int, input().split()))
a.sort()
k = n - 1
for i in range(3, n):
	if a[i] != a[2]:
		k = i - 1
		break
if a[1] != a[2]:
	print(k - 1)
elif a[0] != a[1]:
	print(k * (k - 1) // 2)
elif a[0] == a[1]:
	ans = (k + 1) * k * (k - 1) // 6
	print(ans)


from math import factorial as f
a = int(input())
z = sorted(map(int, input().split()))
(x, x1, x2) = (1, 1, 1)
(y, y1, y2) = (1, 1, 1)
i = 3
while i < a and z[i] == z[2]:
	x2 += 1
	i += 1
if z[1] == z[2]:
	x1 += x2
	x2 = 0
	y1 += y2
	y2 = 0
if z[0] == z[1]:
	x += x1
	x1 = 0
	y += y1
	y1 = 0
k = lambda x, y: f(x) // (f(x - y) * f(y))
print(k(x, y) * k(x1, y1) * k(x2, y2))


n = int(input())
tab = sorted([int(x) for x in input().split()])
a = tab.count(tab[0])
b = tab.count(tab[1])
c = tab.count(tab[2])
if tab[0] == tab[1] and tab[1] == tab[2]:
	print(a * (a - 1) * (a - 2) // 6)
elif tab[0] == tab[1]:
	print(c)
elif tab[1] == tab[2]:
	print(b * (b - 1) // 2)
else:
	print(c)


n = int(input())
a = input().split()
for i in range(n):
	a[i] = int(a[i])
from math import factorial

def delete(l, n):
	for i in range(len(l)):
		if l[i] != n:
			return l[i:]

def comb(n, k):
	return factorial(n) // (factorial(k) * factorial(n - k))

def count(l, n):
	mi = l[0]
	c = l.count(mi)
	if c >= n:
		return comb(c, n)
	else:
		return count(delete(l, mi), n - c)
a.sort()
print(count(a, 3))


n = eval(input())
e = []
for i in input().split(' '):
	e.append(int(i))
e.sort()
(a, b, c) = (e[0], e[1], e[2])
pos = 2
while pos < n and e[pos] == c:
	pos = pos + 1
count = pos - 2
if b != c:
	print(count)
elif a != b:
	print(count * (count + 1) // 2)
else:
	print(count * (count + 1) * (count + 2) // 6)


from collections import Counter
n = int(input())
a = sorted(map(int, input().split()))
c = Counter(a)
if a[0] == a[1] == a[2]:
	k = c[a[0]]
	print(k * (k - 1) * (k - 2) // 6)
elif a[1] == a[2]:
	k = c[a[1]]
	print(k * (k - 1) // 2)
else:
	print(c[a[2]])


n = int(input().strip())
ais = list(map(int, input().strip().split()))
ais.sort()
res = [1]
l = 1
while l < 3:
	if ais[l] != ais[l - 1]:
		res.append(0)
	res[-1] += 1
	l += 1
while l < n and ais[l] == ais[l - 1]:
	res[-1] += 1
	l += 1
if res[-1] == l:
	print(l * (l - 1) * (l - 2) // 6)
elif res[-1] == l - 1:
	print((l - 1) * (l - 2) // 2)
else:
	print(l - 2)


n = input()
a = input().split()
a = [int(x) for x in a]
a.sort()
y = a[2]
arr = [x for x in a if x == y]
ns = len(arr)
if a[0] == y:
	print(int(ns * (ns - 1) * (ns - 2) / 6))
elif a[1] == y:
	print(int(ns * (ns - 1) / 2))
else:
	print(ns)


n = int(input())
a = list(map(int, input().split()))
a.sort()
if a[0] < a[1] < a[2] or (a[0] == a[1] and a[1] < a[2]):
	print(a.count(a[2]))
elif a[0] < a[1] and a[1] == a[2]:
	cnt = a.count(a[2])
	print(cnt * (cnt - 1) // 2)
else:
	cnt = a.count(a[0])
	print(cnt * (cnt - 1) * (cnt - 2) // 6)


from math import factorial

def c(n, k):
	return factorial(n) // factorial(k) // factorial(n - k)
n = int(input())
a = list(map(int, input().split()))
a.sort()
(f, s, t) = (0, 0, 0)
(i, j, k) = (0, 0, 0)
f = a[:3].count(a[0])
if f == 1:
	s = a[:3].count(a[1])
	if s == 1:
		t = 1
elif f == 2:
	s = 1
p = 1
while p < n and a[p] == a[p - 1]:
	p += 1
i = p
if p < n:
	p += 1
	while p < n and a[p] == a[p - 1]:
		p += 1
	j = p - i
	if p < n:
		p += 1
		while p < n and a[p] == a[p - 1]:
			p += 1
		k = p - j - i
print(c(i, f) * c(j, s) * c(k, t))


from math import factorial as f

def ncr(n, r):
	return f(n) // (f(r) * f(n - r))
n = int(input())
l = list(map(int, input().split()))
l.sort()
mn = min(l)
p = sum((1 for x in l if x == mn))
mn2 = max(l)
for x in l:
	if mn < x < mn2:
		mn2 = x
q = sum((1 for x in l if x == mn2))
mn3 = max(l)
for x in l:
	if mn2 < x < mn3:
		mn3 = x
r = sum((1 for x in l if x == mn3))
if p >= 3:
	print(ncr(p, 3))
else:
	if p == 2:
		print(q)
	if p == 1:
		if q == 1:
			print(r)
		else:
			print(ncr(q, 2))


INF = 1e+18

def make_pair_array(n):
	a = []
	for i in range(0, n):
		a.append([0] * 2)
	return a

def cnt_min(b, lst, k, n):
	a = make_pair_array(n)
	min_el = INF
	for i in lst:
		if b[i] == min_el:
			a[i][1] = a[i + k][1] + 1
		elif min_el == INF or b[i] < min_el:
			min_el = b[i]
			a[i][1] = 1
		else:
			a[i][1] = a[i + k][1]
		a[i][0] = min_el
	return a

def main():
	n = int(input())
	a = [int(x) for x in input().split()]
	a.sort()
	min_mul = a[0] * a[1] * a[2]
	left = cnt_min(a, range(0, n), -1, n)
	right = cnt_min(a, range(n - 1, -1, -1), 1, n)
	ans = 0
	for i in range(1, n - 1):
		p = a[i] * left[i - 1][0] * right[i + 1][0]
		if p == min_mul:
			ans += left[i - 1][1] * right[i + 1][1]
	print(ans)
main()


n = int(input())
a = sorted(list(map(int, input().split())))
if a[0] != a[1] and a[1] != a[2]:
	print(a.count(a[2]))
elif a[0] != a[1] and a[1] == a[2]:
	t = a.count(a[1])
	print(t * (t - 1) // 2)
elif a[0] == a[1] and a[1] != a[2]:
	print(a.count(a[2]))
else:
	t = a.count(a[0])
	print(t * (t - 1) * (t - 2) // 6)


n = int(input())
A = list(map(int, input().split(' ')))
A.sort()
(ia, ib, ic) = (0, 0, 0)
while ia < n and A[ia] == A[0]:
	ia += 1
while ia + ib < n and A[ia + ib] == A[1]:
	ib += 1
while ia + ib + ic < n and A[ia + ib + ic] == A[2]:
	ic += 1
if ib == ic == 0:
	print(ia * (ia - 1) * (ia - 2) // 6)
elif ic == 0:
	print(ia * ib * (ib - 1) // 2)
elif ib == 0:
	print(ic * ia * (ia - 1) // 2)
else:
	print(ia * ib * ic)


n = int(input())
a = list(map(int, input().strip().split()))
d = dict()
for i in range(n):
	try:
		d[a[i]] += 1
	except:
		d[a[i]] = 1
l = list(d.keys())
l.sort()
n = len(l)
if n == 1:
	a = d[l[0]]
	print(a * (a - 1) * (a - 2) // 6)
elif n == 2:
	(a, b) = (d[l[0]], d[l[1]])
	if a >= 3:
		print(a * (a - 1) * (a - 2) // 6)
	elif a == 2:
		print(b)
	else:
		print(b * (b - 1) // 2)
else:
	(a, b, c) = (d[l[0]], d[l[1]], d[l[2]])
	if a >= 3:
		print(a * (a - 1) * (a - 2) // 6)
	elif a == 2:
		print(b)
	elif b >= 2:
		print(b * (b - 1) // 2)
	else:
		print(c)


n = int(input())
a = list(map(int, input().split()))
a.sort()
x = list(set(a[0:3]))
if len(x) == 1:
	c = a.count(x[0])
	print(c * (c - 1) * (c - 2) // 6)
if len(x) == 2:
	c = a.count(x[0])
	c1 = a.count(x[1])
	if c == 1:
		print(c1 * (c1 - 1) // 2)
	else:
		print(c1)
if len(x) == 3:
	c = a.count(x[2])
	print(c)


n = int(input())
A = list(map(int, input().split()))
A.sort()
p = A[0] * A[1] * A[2]
c = 1
for i in range(3, n):
	if A[i] == A[2]:
		c += 1
	else:
		break
if A[0] == A[1] == A[2]:
	print((c + 2) * (c + 1) * c // 6)
elif A[1] == A[2]:
	print((c + 1) * c // 2)
else:
	print(c)


import sys
input = sys.stdin.readline
from collections import defaultdict as dc
from collections import Counter
from bisect import bisect_right, bisect_left, bisect
import math
from operator import itemgetter
from heapq import heapify, heappop, heappush
n = int(input())
l = sorted(list(map(int, input().split())))
x = l[2]
c = 0
for i in l:
	if i == x:
		c += 1
if l[0] == l[1] and l[0] == l[2]:
	print(c * (c - 1) * (c - 2) // 6)
elif l[1] == l[2]:
	print(c * (c - 1) // 2)
else:
	print(c)


def c(x, y):
	a = b = 1
	for i in range(y):
		a *= x - i
		b *= y - i
	return int(a / b)
n = int(input())
a = list(map(int, input().split()))
if n < 3:
	print(0)
a.sort()
(x1, x2, x3) = (a[0], a[1], a[2])
count = 0
for i in range(n):
	if a[i] == x3:
		count += 1
if x1 == x2 and x2 == x3:
	print(c(count, 3))
elif x1 < x2 and x2 == x3:
	print(c(count, 2))
else:
	print(count)


def ncr(n, r):
	res = 1
	for i in range(1, r + 1):
		res = res * (n + 1 - i) // i
	return res
n = int(input())
arr = [*map(int, input().split())]
(a, b, c) = sorted(arr)[:3]
(ca, cb, cc) = (arr.count(a), arr.count(b), arr.count(c))
if a == b == c:
	print(ncr(ca, 3))
elif a == b:
	print(ncr(ca, 2) * cc)
elif b == c:
	print(ncr(cb, 2) * ca)
else:
	print(ca * cb * cc)


from math import factorial as fact
from math import inf
N = int(input())
nums = list(map(int, input().split(' ')))
mins = [inf, inf, inf]
for a in nums:
	if a < mins[0]:
		mins[2] = mins[1]
		mins[1] = mins[0]
		mins[0] = a
	elif a < mins[1]:
		mins[2] = mins[1]
		mins[1] = a
	elif a < mins[2]:
		mins[2] = a
if mins[0] == mins[1]:
	if mins[1] == mins[2]:
		reps = {mins[0]: 3}
	else:
		reps = {mins[0]: 2, mins[2]: 1}
elif mins[1] == mins[2]:
	reps = {mins[0]: 1, mins[1]: 2}
else:
	reps = {mins[0]: 1, mins[1]: 1, mins[2]: 1}
ans = 1
for (key, m) in reps.items():
	n = nums.count(key)
	ans *= fact(n) / (fact(m) * fact(n - m))
print(int(ans))


n = map(int, input())
l = list(map(int, input().split()))
d = {}
for i in range(len(l)):
	if l[i] in d.keys():
		d[l[i]] += 1
	else:
		d[l[i]] = 1
ll = sorted(d.keys())
ans = 0
a = d[ll[0]]
if len(d) > 1:
	b = d[ll[1]]
if len(d) > 2:
	c = d[ll[2]]
if a >= 3:
	ans += a * (a - 1) * (a - 2) / 6
elif a == 2:
	ans += a * (a - 1) / 2 * b
elif a == 1:
	ans += a
	if b >= 2:
		ans *= b * (b - 1) / 2
	else:
		ans *= b * c
print(int(ans))


def f(n, r):
	if r == 1:
		return n
	elif r == 2:
		return n * (n - 1) // 2
	else:
		return n * (n - 1) * (n - 2) // 6
n = int(input())
a = list(map(int, input().split()))
dic = {}
for ai in a:
	if ai in dic:
		dic[ai] += 1
	else:
		dic[ai] = 1
a = list(sorted(set(a)))
ans = 1
i = 0
cnt = 3
while 0 < cnt:
	x = dic[a[i]]
	if cnt < x:
		ans *= f(x, min(x, cnt))
	cnt -= x
	i += 1
print(ans)


read = lambda : map(int, input().split())
n = int(input())
a = sorted(read())
(c1, c2, c3) = (a.count(a[0]), a.count(a[1]), a.count(a[2]))
if a[0] == a[1] == a[2]:
	ans = c1 * (c1 - 1) * (c1 - 2) // 6
elif a[1] != a[2]:
	ans = c3
else:
	ans = c2 * (c2 - 1) // 2
print(ans)


n = int(input())
A = list(map(int, input().split()))
cnt = {}
for i in A:
	if i in cnt:
		cnt[i] += 1
	else:
		cnt[i] = 1
sA = sorted(list(set(A)))

def nc3(n):
	return n * (n - 1) * (n - 2) // 6

def nc2(n):
	return n * (n - 1) // 2
if len(sA) > 3:
	sA = sA[:3]
if cnt[sA[0]] >= 3:
	print(nc3(cnt[sA[0]]))
elif cnt[sA[0]] == 2:
	print(nc2(cnt[sA[0]]) * cnt[sA[1]])
elif cnt[sA[1]] >= 2:
	print(cnt[sA[0]] * nc2(cnt[sA[1]]))
else:
	print(cnt[sA[2]])


from functools import reduce

def nCr(a, b):
	return reduce(lambda i, j: i * j, range(a, a - b, -1)) // reduce(lambda i, j: i * j, range(b, 0, -1))

def main():
	size = int(input())
	ls = sorted(list(map(int, input().rstrip().split())))
	best = ls[2]
	count = (1 if ls[0] == ls[2] else 0) + (1 if ls[1] == ls[2] else 0) + 1
	num = len(list(filter(lambda x: x == best, ls)))
	print(nCr(num, count))
main()


n = int(input())
list = list(map(int, input().split()))
list.sort()
(a, b, c) = (list[0], list[1], list[2])
rslt = 0
for i in list[2:n]:
	if c == i:
		rslt += 1
	else:
		break
if c != b:
	print(rslt)
elif a != b:
	print(rslt * (rslt + 1) // 2)
else:
	print(rslt * (rslt + 1) * (rslt + 2) // 6)


input()
s = sorted(map(int, input().split()))
(a, b, c) = s[:3]
x = s.count(c)
y = x * (x - 1) // 2
z = y * (x - 2) // 3
print(x if b != c else y if a != b else z)


n = int(input())
a = list(map(int, input().split()))
a.sort()
if a[0] == a[1] == a[2]:
	answer = a.count(a[0])
	answer = answer * (answer - 1) * (answer - 2) // 6
elif a[0] <= a[1] < a[2]:
	answer = a.count(a[2])
elif a[0] < a[1] == a[2]:
	answer = a.count(a[2])
	answer = answer * (answer - 1) // 2
print(answer)


n = int(input())
a = [int(i) for i in input().split()]
a.sort()
count = 0
c1 = 0
c2 = 0
for i in range(n):
	if a[i] == a[2]:
		count += 1
		if i == 0:
			c1 = 1
		if i == 1:
			c2 = 1
if c1 == 1:
	print(count * (count - 1) * (count - 2) // (3 * 2))
elif c2 == 1:
	print(count * (count - 1) // 2)
else:
	print(count)


import sys
import bisect
from math import ceil, floor, factorial

def c(a, b):
	return int(factorial(a) / (factorial(b) * factorial(a - b)))
RI = lambda : [int(x) for x in sys.stdin.readline().split()]
ri = lambda : sys.stdin.readline().strip()
mod = 10 ** 9 + 7
n = int(ri())
a = RI()
dic = {}
for i in range(len(a)):
	if a[i] not in dic:
		dic[a[i]] = 1
	else:
		dic[a[i]] += 1
num = [i for i in dic]
num.sort()
k = 3
i = 0
for i in range(len(num)):
	if dic[num[i]] >= k:
		break
	else:
		k -= dic[num[i]]
print(c(dic[num[i]], k))


import itertools
import bisect
import math
from collections import *
import os
import sys
from io import BytesIO, IOBase
ii = lambda : int(input())
lmii = lambda : list(map(int, input().split()))
li = lambda : list(input())
mii = lambda : map(int, input().split())
msi = lambda : map(str, input().split())

def main():
	n = ii()
	a = sorted(lmii())
	c = Counter(a)
	if a[0] == a[1] == a[2]:
		ans = 0
		for i in range(c[a[0]] - 2, 0, -1):
			ans += i * (i + 1) // 2
		print(ans)
	elif a[1] == a[2]:
		print((c[a[1]] - 1) * c[a[1]] // 2)
	else:
		print(c[a[2]])
	pass
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


from math import factorial as f
infinity = 10 ** 9 + 1

def find_min(arr, exclude):
	min_elem = infinity
	count = 0
	for elem in arr:
		if elem not in exclude and elem < min_elem:
			min_elem = elem
			count = 1
		elif elem == min_elem:
			count += 1
	if min_elem == infinity:
		(min_elem, count) = (0, 0)
	return (min_elem, count)
_ = int(input())
arr = [int(i) for i in input().split()]
(a_min, a_count) = find_min(arr, [])
(b_min, b_count) = find_min(arr, [a_min])
(c_min, c_count) = find_min(arr, [a_min, b_min])
combinations = lambda n, m: f(n) // f(m) // f(n - m)
mins = [a_count, b_count, c_count]
sum_count = 0
res = 1
i = 0
while sum_count < 3 and i < len(mins):
	can_take = mins[i]
	can_take = min(can_take, 3 - sum_count)
	sum_count += can_take
	res *= combinations(mins[i], can_take)
	i += 1
print(res)


n = int(input())
li = list(map(int, input().split()))
li.sort()
i = 2
cnt = 0
while i < n and li[i] == li[2]:
	cnt += 1
	i += 1
if li[0] == li[2]:
	cnt += 2
	ans = cnt * (cnt - 1) * (cnt - 2) // 6
	print(ans)
elif li[1] == li[2]:
	cnt += 1
	ans = cnt * (cnt - 1) // 2
	print(ans)
else:
	print(cnt)


n = input()
a = input()
a = a.split(' ')
a = list(map(int, a))
b = [10 ** 9, 10 ** 9, 10 ** 9]
for i in a:
	if i < b[0]:
		b[2] = b[1]
		b[1] = b[0]
		b[0] = i
	elif i < b[1]:
		b[2] = b[1]
		b[1] = i
	elif i < b[2]:
		b[2] = i
if len(set(b)) == 1:
	s = 0
	for i in a:
		if i == b[0]:
			s += 1
	print(int(s * (s - 1) * (s - 2) / 6))
elif len(set(b)) == 2:
	(s, t) = (0, 0)
	for i in a:
		if i == b[0]:
			s += 1
		elif i == b[2]:
			t += 1
	if b[1] == b[0]:
		print(int(s * (s - 1) / 2) * t)
	else:
		print(int(t * (t - 1) / 2) * s)
else:
	(s, t, r) = (0, 0, 0)
	for i in a:
		if i == b[0]:
			s += 1
		elif i == b[1]:
			t += 1
		elif i == b[2]:
			r += 1
	print(s * t * r)


import sys
from collections import defaultdict
input = sys.stdin.readline
(d, n) = (defaultdict(int), int(input()))
s = sorted(list(map(int, input().split())))
for i in s:
	d[i] += 1
if s[2] != s[1]:
	print(d[s[2]])
elif s[2] == s[1] and s[1] != s[0]:
	print(d[s[2]] * (d[s[2]] - 1) // 2)
else:
	print(d[s[0]] * (d[s[0]] - 1) * (d[s[0]] - 2) // 6)


import sys, math, queue, bisect
MOD = 10 ** 9 + 7
sys.setrecursionlimit(1000000)
n = int(input())
a = list(map(int, input().split()))
a.sort()
d = {}
for ai in a:
	if ai in d:
		d[ai] += 1
	else:
		d[ai] = 1
x = []
for i in range(3):
	if a[i] not in x:
		x.append(a[i])
if len(x) == 1:
	c = d[x[0]]
	print(c * (c - 1) * (c - 2) // 6)
elif len(x) == 2:
	if d[x[0]] == 2:
		print(d[x[1]])
	else:
		c = d[x[1]]
		print(c * (c - 1) // 2)
else:
	print(d[x[0]] * d[x[1]] * d[x[2]])


import sys
input = sys.stdin.readline
from collections import Counter
n = int(input())
a = list(map(int, input().split()))
a.sort()
cnt = Counter(a)
if a[0] == a[1] == a[2]:
	n = cnt[a[0]]
	print(n * (n - 1) * (n - 2) // 6)
elif a[0] == a[1]:
	n = cnt[a[0]]
	print(n * (n - 1) // 2 * cnt[a[2]])
elif a[1] == a[2]:
	n = cnt[a[1]]
	print(cnt[a[0]] * n * (n - 1) // 2)
else:
	print(cnt[a[0]] * cnt[a[1]] * cnt[a[2]])


import math

def bin_coeff(p, n):
	ret_val = 1
	for i in range(p):
		ret_val *= n - i
		ret_val //= i + 1
	return ret_val
n = int(input())
a = [int(x) for x in input().split()]
b = sorted(a)
from itertools import groupby
c = [len(list(group)) for (key, group) in groupby(b)]
sum = 3
i = 0
while sum - c[i] > 0:
	sum -= c[i]
	i += 1
ans = bin_coeff(sum, c[i])
print(ans)


import sys
import bisect
from bisect import bisect_left as lb
from bisect import bisect_right as rb
input_ = lambda : sys.stdin.readline().strip('\r\n')
from math import log
from math import gcd
from math import atan2, acos
from random import randint
sa = lambda : input_()
sb = lambda : int(input_())
sc = lambda : input_().split()
sd = lambda : list(map(int, input_().split()))
sflo = lambda : list(map(float, input_().split()))
se = lambda : float(input_())
sf = lambda : list(input_())
flsh = lambda : sys.stdout.flush()
mod = 10 ** 9 + 7
mod1 = 998244353
gp = []
cost = []
dp = []
mx = []
ans1 = []
ans2 = []
special = []
specnode = []
a = 0
kthpar = []

def dfs(root, par):
	if par != -1:
		dp[root] = dp[par] + 1
	for i in range(1, 20):
		if kthpar[root][i - 1] != -1:
			kthpar[root][i] = kthpar[kthpar[root][i - 1]][i - 1]
	for child in gp[root]:
		if child == par:
			continue
		kthpar[child][0] = root
		dfs(child, root)
ans = 0
b = []

def dfs2(root, par, d):
	global gp, dp
	dp[root] = d
	for child in gp[root]:
		if child == par:
			continue
		dfs2(child, root, d + 1)

def hnbhai(tc):
	n = sb()
	a = sd()
	a.sort()
	prod = a[0] * a[1] * a[2]
	if a[0] == a[1] == a[2]:
		abe = a.count(a[0])
		print(abe * (abe - 1) * (abe - 2) // 6)
		return
	if a[1] == a[2]:
		abe = a.count(a[1])
		print(abe * (abe - 1) // 2)
		return
	print(a.count(a[2]))
for _ in range(1):
	hnbhai(_ + 1)


a = int(input())
b = input()
b = b.split(' ')
s = []
for i in range(len(b)):
	b[i] = int(b[i])
	s.append(b[i])
s.sort()
f1 = b.count(s[0])
b.remove(s[0])
f2 = b.count(s[1])
b.remove(s[1])
f3 = b.count(s[2])
b.remove(s[2])
f4 = f1 * f2 * f3
if s[1] == s[2] and s[2] == s[0]:
	f4 = f4 // 6
if s[1] == s[2] and s[2] != s[0]:
	f4 = f4 // 2
if s[1] == s[0] and s[0] != s[2]:
	f4 = f4 // 2
if s[2] == s[0] and s[1] != s[2]:
	f4 = f4 // 2
print(f4)


from math import factorial

def C(k, n):
	return factorial(n) // factorial(k) // factorial(n - k)
input()
a = [int(x) for x in input().split()]
counter = {k: 0 for k in sorted(a)[:3]}
for n in a:
	if n in counter:
		counter[n] += 1
if len(counter) == 1:
	answer = C(3, next(iter(counter.values())))
elif len(counter) == 2:
	if counter[min(counter)] == 2:
		answer = counter[max(counter)]
	else:
		answer = C(2, counter[max(counter)])
else:
	answer = counter[max(counter)]
print(answer)


input()
l = sorted(list(map(int, input().split())))
a = l.count(l[0])
b = l.count(l[1])
c = l.count(l[2])
if a > 2:
	print(a * (a - 1) * (a - 2) // 6)
elif a == 1 and b > 1:
	print(b * (b - 1) // 2)
else:
	print(c)


n = int(input())
a = list(map(int, input().split()))
pre = a[:]
cnt1 = [1] * n
for i in range(len(a)):
	if i == 0:
		continue
	pre[i] = pre[i - 1]
	cnt1[i] = cnt1[i - 1]
	if a[i] < pre[i]:
		pre[i] = a[i]
		cnt1[i] = 1
	elif a[i] == pre[i]:
		cnt1[i] += 1
pre2 = [10 ** 30] * n
cnt2 = [0] * n
for i in range(n):
	if i == 0:
		continue
	pre2[i] = pre2[i - 1]
	cnt2[i] = cnt2[i - 1]
	te = a[i] * pre[i - 1]
	if te < pre2[i]:
		pre2[i] = te
		cnt2[i] = cnt1[i - 1]
	elif te == pre2[i]:
		cnt2[i] += cnt1[i - 1]
ans = 10 ** 30
cnt = 0
for i in range(n):
	if i < 2:
		continue
	t = a[i] * pre2[i - 1]
	if t < ans:
		ans = t
		cnt = cnt2[i - 1]
	elif ans == t:
		cnt += cnt2[i - 1]
print(cnt)


n = int(input())
u = list(map(int, input().split()))
inf = 10 ** 9 + 1
mc = [0] * 3
mv = [inf] * 3
for i in range(n):
	if u[i] < mv[0]:
		mv = [u[i], mv[0], mv[1]]
		mc = [1, mc[0], mc[1]]
	elif u[i] == mv[0]:
		mc[0] += 1
	elif u[i] < mv[1]:
		mv = [mv[0], u[i], mv[1]]
		mc = [mc[0], 1, mc[1]]
	elif u[i] == mv[1]:
		mc[1] += 1
	elif u[i] < mv[2]:
		mv[2] = u[i]
		mc[2] = 1
	elif u[i] == mv[2]:
		mc[2] += 1
if mc[0] >= 3:
	p = mc[0]
	print(p * (p - 1) * (p - 2) // 6)
elif mc[0] + mc[1] >= 3:
	(p1, p2) = mc[:2]
	if p1 == 1:
		print(p2 * (p2 - 1) // 2)
	else:
		print(p2)
else:
	print(mc[2])


k = int(input())
a = list(map(int, input().split()))
a.sort()
flag_three_more = False
flag_two_more = False
flag_one_more = False
if len(a) == 3:
	print('1')
else:
	count = 1
	i = 3
	while a[i] == a[2]:
		flag_three_more = True
		i += 1
		count += 1
		if i == len(a):
			break
	if a[2] == a[1] and flag_three_more:
		flag_two_more = True
	if a[1] == a[0] and flag_two_more:
		flag_one_more = True
	if flag_one_more:
		ans = count * (count + 1) * (count + 2) // 6
	elif flag_two_more:
		ans = count * (count + 1) // 2
	elif flag_three_more:
		ans = count
	else:
		ans = 1
	print(ans)


def fatorial(n):
	if n == 0:
		return 1
	else:
		return fatorial(n - 1) * n
qtd = int(input())
valores = list(map(int, input().split()))
valores.sort()
if valores.count(valores[0]) == 1:
	if valores.count(valores[1]) == 1:
		print(valores.count(valores[2]))
	else:
		aux = valores.count(valores[1])
		print(int(aux * (aux - 1) / 2))
elif valores.count(valores[0]) == 2:
	print(valores.count(valores[2]))
else:
	aux = valores.count(valores[2])
	x = int(aux * (aux - 1) * (aux - 2) / 6)
	print(x)


from math import factorial
input()
a = sorted(map(int, input().split()))
d = {}
for i in a:
	if i in d:
		d[i] += 1
	else:
		d[i] = 1
numbers = set(a[:3])
lN = len(numbers)

def nCr(n, r):
	return factorial(n) // (factorial(n - r) * factorial(r))
if lN == 1:
	print(nCr(d[a[0]], 3))
elif lN == 2:
	if a[0] == a[1]:
		print(d[a[2]])
	else:
		print(nCr(d[a[2]], 2))
else:
	print(d[a[2]])