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.

Difficulty: interview

Starter code:

Solutions:
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())
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)


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]


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


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=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)

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)


## 2

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)
    


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())
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)


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



# -*- coding: utf-8 -*-
"""
Created on Thu Jun 15 20:41:20 2017

@author: prophet
"""

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)

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)
    




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())
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
    else:
        if 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]
    else:
        if 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]
    else:
        if ans==t:
            cnt+=cnt2[i-1]

print(cnt)

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))
        return
    else:
        web-=a.count(min(a))
        e=min(a)
        while e in a:
            a.remove(e)

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())
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)


import os
n =int(input())
arr=[int(x) for x in input().strip().split()]

# arr=[1 for x in range(0,100000)]
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))





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)
        else:
            if len(b) <= 2:
                print(0)
            else:
                print(c[b[2]])


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)


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)


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

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 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}
else:
    if 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))