Emily's birthday is next week and Jack has decided to buy a present for her. He knows she loves books so he goes to the local bookshop, where there are n books on sale from one of m genres.

In the bookshop, Jack decides to buy two books of different genres.

Based on the genre of books on sale in the shop, find the number of options available to Jack for choosing two books of different genres for Emily. Options are considered different if they differ in at least one book.

The books are given by indices of their genres. The genres are numbered from 1 to m.


-----Input-----

The first line contains two positive integers n and m (2 ≤ n ≤ 2·10^5, 2 ≤ m ≤ 10) — the number of books in the bookstore and the number of genres.

The second line contains a sequence a_1, a_2, ..., a_{n}, where a_{i} (1 ≤ a_{i} ≤ m) equals the genre of the i-th book.

It is guaranteed that for each genre there is at least one book of that genre.


-----Output-----

Print the only integer — the number of ways in which Jack can choose books.

It is guaranteed that the answer doesn't exceed the value 2·10^9.


-----Examples-----
Input
4 3
2 1 3 1

Output
5

Input
7 4
4 2 3 1 2 4 3

Output
18



-----Note-----

The answer to the first test sample equals 5 as Sasha can choose:  the first and second books,  the first and third books,  the first and fourth books,  the second and third books,  the third and fourth books.

Difficulty: EASY
Tags: Implementation

Constructive algorithms

Starter code:

Solutions:
(n, m) = map(int, input().split())
a = list(map(int, input().split()))
p = [0] * m
for i in range(n):
	p[a[i] - 1] += 1
ans = 0
for i in range(m):
	ans += p[i] * (n - p[i])
print(ans // 2)


(n, m) = list(map(int, input().split()))
L = list(map(int, input().split()))
T = [0 for _ in range(m)]
for k in range(n):
	T[L[k] - 1] += 1
r = 0
for i in range(m - 1):
	for j in range(i + 1, m):
		r += T[i] * T[j]
print(r)


(n, m) = map(int, input().split())
a = list(map(int, input().split()))
arr = [0 for _ in range(m + 1)]
for i in a:
	arr[i] += 1
ans = 0
for i in range(1, m + 1):
	for j in range(i + 1, m + 1):
		ans += arr[i] * arr[j]
print(ans)


(n, m) = map(int, input().split())
a = map(int, input().split())
count = [0] * (m + 1)
ans = 0
for x in a:
	count[x] += 1
for x in count:
	ans += (n - x) * x
print(ans // 2)


a = input().split()
n = int(a[0])
m = int(a[1])
kn = []
k = input().split()
for i in range(n):
	kn += [int(k[i])]
c = 0
for i in range(m):
	c += kn.count(i + 1) * (n - kn.count(i + 1))
print(int(c / 2))


(n, m) = map(int, input().split())
a = list(map(int, input().split()))
b = [0] * (m + 1)
for i in a:
	b[i] += 1
r = n * (n - 1) // 2
for x in b:
	r -= x * (x - 1) // 2
print(r)


(n, m) = map(int, input().split())
b = list(map(int, input().split()))
db = {}
for item in b:
	if item in db:
		db[item] += 1
	else:
		db[item] = 1
sb = 0
for key in db:
	sb += db[key] * (db[key] - 1)
sg = n * (n - 1)
ans = (sg - sb) / 2
print(int(ans))


(n, m) = map(int, input().split())
a = [0] * m
for v in map(int, input().split()):
	a[v - 1] += 1
s = 0
for i in range(m):
	for j in range(i + 1, m):
		s += a[i] * a[j]
print(s)


(n, m) = map(int, input().split())
genre = [0] * 11
ar = list(map(int, input().split()))
for x in ar:
	genre[x] += 1
total = n * (n - 1) // 2
for y in genre:
	total = total - y * (y - 1) // 2
print(total)


(n, m) = map(int, input().rstrip().split())
array = list(map(int, input().rstrip().split()))
s = set(array)
sum1 = sum(range(n))
sum2 = 0
for i in s:
	cnt = array.count(i)
	if cnt > 1:
		sum2 += sum(range(cnt))
print(sum1 - sum2)


(n, m) = map(int, input().split())
a = list(map(int, input().split()))
b = list(set(a))
ans = 0
for i in range(m - 1):
	for j in range(i + 1, m):
		ans += a.count(b[i]) * a.count(b[j])
print(ans)


Ent = [int(i) for i in input().split()]
Ent1 = [int(i) for i in input().split()]
List = []
for i in range(Ent[1]):
	List.append(0)
for i in Ent1:
	List[i - 1] += 1
cont = Ent[0] * (Ent[0] - 1) / 2
for i in List:
	if i > 1:
		cont -= i * (i - 1) / 2
print(int(cont))


import sys
(n, m) = map(int, input().split())
a = list(map(int, input().split()))
cnt = [0] * 11
for i in range(len(a)):
	cnt[a[i]] += 1
ans = 0
for i in range(1, m + 1):
	for j in range(i + 1, m + 1):
		ans += cnt[i] * cnt[j]
print(ans)


def function():
	totalDrives = int(input())
	fileSize = int(input())
	drives = []
	for element in range(totalDrives):
		temp = int(input())
		drives.append(temp)
	drives.sort()
	currentSize = 0
	driveCount = 0
	while currentSize < fileSize:
		currentSize += drives.pop()
		driveCount += 1
	return driveCount

def genre():
	temp = input().split()
	bookCount = int(temp[0])
	genres = int(temp[1])
	temp = input().split()
	books = list(map(int, temp))
	books.sort()
	temp = 0
	bookGenre = [0] * genres
	for book in books:
		if book == temp:
			bookGenre[book - 1] += 1
		else:
			temp += 1
			bookGenre[book - 1] = 1
	combinations = 0
	for genre in bookGenre:
		combinations += genre * (bookCount - genre)
	return int(combinations / 2)
print(genre())


(n, m) = map(int, input().split())
books = list(map(int, input().split()))
ja = [0 for p in range(11)]
ans = 0
for i in books:
	ja[i] += 1
s = 0
for i in ja:
	k = i
	d = n - i
	s = k * d
	ans += s
	n -= i
print(ans)


import logging
import copy
import sys
logging.basicConfig(stream=sys.stderr, level=logging.DEBUG)

def solve(n, m, lines):
	lst = [0] * m
	for g in lines:
		lst[g - 1] += 1
	total = 0
	for i in range(m):
		for j in range(i + 1, m):
			total += lst[i] * lst[j]
	return total

def main():
	firstLine = input().split()
	firstLine = list(map(int, firstLine))
	(n, m) = (firstLine[0], firstLine[1])
	inputLines = input().split()
	inputLines = list(map(int, inputLines))
	print(solve(n, m, inputLines))

def log(*message):
	logging.debug(message)
main()


__author__ = 'Utena'
(n, m) = map(int, input().split())
s = list(map(int, input().split()))
v = [0] * m
for i in s:
	v[i - 1] += 1
t = 0
for j in range(m):
	t1 = v[j]
	t2 = 0
	for r in range(j + 1, m):
		t2 += t1 * v[r]
	t += t2
print(t)


(n, k) = list(map(int, input().split()))
t = list(map(int, input().split()))
p = 0
v = [0] * k
for i in range(1, k + 1):
	v[i - 1] = t.count(i)
for b in range(k - 1):
	for j in range(b + 1, k):
		p += v[b] * v[j]
print(p)


(n, m) = map(int, input().split())
a = list(map(int, input().split()))
cnt = [0] * (m + 1)
for x in a:
	cnt[x] += 1
ans = 0
for x in range(1, m):
	y = x + 1
	while y <= m:
		ans += cnt[x] * cnt[y]
		y += 1
print(ans)


(n, m) = map(int, input().split())
l = list(map(int, input().split()))
s = 0
d = {}
for i in range(n):
	if l[i] in d:
		d[l[i]] = d[l[i]] + 1
	else:
		d[l[i]] = 1
for i in d:
	s = s + d[i] * (d[i] - 1) / 2
print(int(n * (n - 1) / 2 - s))


import operator as op
from functools import reduce

def ncr(n, r):
	r = min(r, n - r)
	numer = reduce(op.mul, range(n, n - r, -1), 1)
	denom = reduce(op.mul, range(1, r + 1), 1)
	return numer // denom
first_line = [int(i) for i in input().split()]
(n, m) = (first_line[0], first_line[1])
books = [int(i) for i in input().split()]
cnt = [0] * m
fact = [0] * (n + 1)
fact[n] = ncr(n, 2)
total_options = fact[n]
for b in books:
	cnt[b - 1] += 1
for i in cnt:
	if i > 1:
		if fact[i] == 0:
			fact[i] = ncr(i, 2)
		total_options -= fact[i]
print(int(total_options))


def main():
	from collections import Counter
	from itertools import combinations
	from operator import mul
	input()
	print(sum((mul(*ab) for ab in combinations(Counter(input().split()).values(), 2))))
main()


(n, m) = map(int, input().split())
a = map(int, input().split())
genres = [0 for _ in range(11)]
for k in a:
	genres[k] += 1
all_comb = n * (n - 1) // 2
each_comb = sum((t * (t - 1) // 2 for t in genres))
print(all_comb - each_comb)


(n, m) = map(int, input().split())
a = list(map(int, input().split()))
genres = []
for i in range(m):
	genres.append(a.count(i + 1))
result = 0
for i in range(m - 1):
	for j in range(i + 1, m):
		result += genres[i] * genres[j]
print(result)


(n, m) = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
l = m * [0]
for i in range(m):
	l[i] = a.count(i + 1)
o = 0
for i in range(m):
	for j in range(m):
		if i != j:
			o += l[i] * l[j]
print(o // 2)


(n, m) = map(int, input().split())
a = list(map(int, input().split()))
cnt = [0] * (m + 1)
for i in a:
	cnt[i] += 1
res = 0
for i in a:
	res += n - cnt[i]
print(res // 2)


(n, k) = map(int, input().split())
t = [0] * (k + 1)
for i in map(int, input().split()):
	t[i] += 1
p = sum(t)
s = 0
for i in range(1, k):
	s += t[i] * (p - t[i])
	p -= t[i]
print(s)


from collections import Counter

class CodeforcesTask609BSolution:

	def __init__(self):
		self.result = ''
		self.n_m = []
		self.genres = []

	def read_input(self):
		self.n_m = [int(x) for x in input().split(' ')]
		self.genres = [int(x) for x in input().split(' ')]

	def process_task(self):
		genre_cnt = Counter(self.genres)
		res = 0
		for first in range(self.n_m[1]):
			for second in range(self.n_m[1]):
				if first != second:
					res += genre_cnt[first + 1] * genre_cnt[second + 1]
		res //= 2
		self.result = str(res)

	def get_result(self):
		return self.result
Solution = CodeforcesTask609BSolution()
Solution.read_input()
Solution.process_task()
print(Solution.get_result())


aa = [int(num) for num in input().split()]
books = [int(num) for num in input().split()]
result = 0
for genre in range(1, aa[1] + 1):
	n = books.count(genre)
	aa[0] -= n
	result += n * aa[0]
print(result)


(n, m) = [int(x) for x in input().split(' ')]
a = [int(x) for x in input().split(' ')]
arr = [0] * m
for i in range(n):
	arr[a[i] - 1] += 1
combinations = 0
for i in range(m - 1):
	for j in arr[i + 1:m]:
		combinations += arr[i] * j
print(combinations)


n = list(map(int, input().split()))
m = list(map(int, input().split()))
cont = []
for i in range(n[1]):
	cont.append(m.count(i + 1))
way = 0
for i in range(1, len(cont)):
	way += sum(cont[i:]) * cont[i - 1]
print(way)


import sys
import os.path
from collections import *
import math
import bisect
if os.path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
else:
	input = sys.stdin.readline
(n, m) = [int(x) for x in input().split()]
arr = [int(x) for x in input().split()]
h = Counter(arr)
arr = []
for i in h:
	arr.append(h[i])
res = 0
for i in range(m - 1):
	for j in range(i + 1, m):
		res += arr[i] * arr[j]
print(res)


from collections import Counter
(n, m) = [int(j) for j in input().split()]
a = [int(j) for j in input().split()]
b = Counter(a)
c = []
for i in range(1, m + 1):
	if b[i] > 0:
		c.append(b[i])
d = 0
for i in range(0, len(c) - 1):
	for j in range(i + 1, len(c)):
		d = d + c[i] * c[j]
print(d)


(n, m) = map(int, input().split())
l = list(map(int, input().split()))
a = m * [0]
for i in range(n):
	a[l[i] - 1] += 1
s = 0
for i in range(m - 1):
	for j in a[i + 1:m]:
		s += a[i] * j
print(s)


(n, m) = map(int, input().split())
a = [0] * (m + 1)
for i in map(int, input().split()):
	a[i - 1] += 1
ans = 0
for i in range(m):
	for j in range(i + 1, m):
		ans += a[i] * a[j]
print(ans)


from bisect import *

def inpList():
	return list(map(int, input().split()))

def inp():
	return int(input())
(n, m) = inpList()
a = inpList()
x = {}
for i in range(1, m + 1):
	x[i] = 0
for i in a:
	x[i] += 1
p = sum((x[i] for i in x))
t = sum((x[i] * x[i] for i in x))
print((p * p - t) // 2)


from collections import *
(n, m) = map(int, input().split())
l = list(map(int, input().split()))
l.sort()
d = defaultdict(int)
for i in l:
	d[i] += 1
x = list(d.values())
s = sum(x)
k = len(x)
c = 0
for i in range(k - 1):
	s = s - x[i]
	c = c + s * x[i]
print(c)


(n, m) = map(int, input().split())
x = 0
a = [int(x) for x in input().split()]
count = 0
summa = 0
for i in range(1, m + 1):
	summa += a.count(i) * (a.count(i) - 1) // 2
summa1 = n * (n - 1) // 2
print(summa1 - summa)


(n, m) = map(int, input().split())
a = list(map(int, input().split()))
count = [0] * (m + 1)
for genre in a:
	count[genre] += 1
ways = 0
for i in range(1, m):
	for j in range(i + 1, m + 1):
		ways += count[i] * count[j]
print(ways)


args = input().split()
n = int(args[0])
m = int(args[1])
genres = input().split()
counts = []
for i in range(len(genres)):
	genres[i] = int(genres[i])
genres.sort()
genres_nodup = list(set(genres))
for i in genres_nodup:
	counts.append(genres.count(i))
ans = 0
for i in range(len(counts) - 1):
	ans += counts[i] * sum(counts[i + 1:])
print(ans)


import unittest
import sys

class Gift:

	def __init__(self, test_inputs=None):
		it = iter(test_inputs.split('\n')) if test_inputs else None

		def uinput():
			return next(it) if it else sys.stdin.readline().rstrip()
		[self.n, self.m] = map(int, uinput().split())
		self.nums = list(map(int, uinput().split()))
		self.genr = [0] * self.m
		for n in self.nums:
			self.genr[n - 1] += 1
		self.summ = sum(self.genr)

	def calculate(self):
		result = 0
		for (i, n) in enumerate(self.nums):
			result += self.summ - self.genr[n - 1]
		return str(result // 2)

class unitTests(unittest.TestCase):

	def test_single_test(self):
		test = '4 3\n2 1 3 1'
		d = Gift(test)
		self.assertEqual(d.n, 4)
		self.assertEqual(d.m, 3)
		self.assertEqual(d.nums, [2, 1, 3, 1])
		self.assertEqual(d.genr, [2, 1, 1])
		self.assertEqual(Gift(test).calculate(), '5')
		test = '7 4\n4 2 3 1 2 4 3'
		self.assertEqual(Gift(test).calculate(), '18')
		test = ''
		test = ''

	def time_limit_test(self, nmax):
		import random
		import timeit
		test = str(nmax) + ' ' + str(nmax) + '\n'
		numnums = [str(i) + ' ' + str(i + 1) for i in range(nmax)]
		test += '\n'.join(numnums) + '\n'
		nums = [random.randint(1, 10000) for i in range(nmax)]
		test += ' '.join(map(str, nums)) + '\n'
		start = timeit.default_timer()
		d = Gift(test)
		calc = timeit.default_timer()
		d.calculate()
		stop = timeit.default_timer()
		print('\nTimelimit Test: ' + '{0:.3f}s (init {1:.3f}s calc {2:.3f}s)'.format(stop - start, calc - start, stop - calc))
sys.setrecursionlimit(100000)
if sys.argv[-1] == '-ut':
	unittest.main(argv=[' '])
sys.stdout.write(Gift().calculate())


(nr_books, __) = input().split(' ')
nr_books = int(nr_books)
books = input().split(' ')
books = [int(book) for book in books]
res = {}
for genre in books:
	try:
		res[genre] = res[genre] + 1
	except KeyError:
		res[genre] = 1
choices = 0
for genre in res.keys():
	nr_books = nr_books - res[genre]
	choices += res[genre] * nr_books
print(choices)


(n, m) = map(int, input().split())
mas = list(map(int, input().split()))
masc = [0] * (m + 1)
for i in range(1, m + 1):
	masc[i] = mas.count(i)
i = 1
var = 0
while masc[i] > 0:
	var += masc[i] * sum(masc[i + 1:])
	i += 1
	if i >= len(masc):
		break
print(var)


from collections import Counter
(n, m) = map(int, input().split())
l = list(map(int, input().split()))
cc = Counter(l)
vals = list(cc.values())
ans = 0
for i in range(m):
	for j in range(i + 1, m):
		ans += vals[i] * vals[j]
print(ans)


(a, b) = map(int, input().split(' '))
l = list(map(int, input().split(' ')))
stot = 0
ssq = 0
for i in range(1, b + 1):
	stot += l.count(i)
	ssq += l.count(i) ** 2
print(int((stot ** 2 - ssq) / 2))


(n, m) = map(int, input().split())
a = list(map(int, input().split()))
res = 0
for i in range(m):
	c = a.count(i + 1)
	res += c * (n - c)
print(res // 2)


(number_of_books, number_of_genres) = map(int, input().split())
count_genres = number_of_genres * [0]
type_of_each_book = list(map(int, input().split()))
for book in type_of_each_book:
	count_genres[book - 1] += 1
total_ways = 0
for (index, count) in enumerate(count_genres):
	total_ways += count * sum(count_genres[index + 1:])
print(total_ways)


def main():
	(n, m) = (int(x) for x in input().split())
	L = [int(x) for x in input().split()]
	print(solver(m, L))

def solver(m, L):
	books = [0] * (m + 1)
	for i in L:
		books[i] += 1
	total = 0
	for i in range(1, len(books)):
		for j in range(i + 1, len(books)):
			total += books[i] * books[j]
	return total
main()


from collections import Counter
(n, m) = map(int, input().split())
a = input().split()
a = dict(Counter(a))
b = []
for i in range(1, m + 1):
	b.append(a[str(i)])
ans = 0
for i in range(m):
	for j in range(i + 1, m):
		ans += int(b[i]) * int(b[j])
print(ans)


(n, m) = list(map(int, input().split()))
l = list(map(int, input().split()))
num = [0] * int(2 * 100000.0 + 5)
for i in l:
	num[i] += 1
ans = n * (n - 1) // 2
for i in num:
	ans -= i * (i - 1) // 2
print(ans)


booksNumAndGenreNum = input().split()
booksNum = int(booksNumAndGenreNum[0])
genreNum = int(booksNumAndGenreNum[0])
books = list(map(int, input().split()))
booksPerGenre = []
for book in books:
	exist = False
	for books in booksPerGenre:
		if books[0] == book:
			books[1] = books[1] + 1
			exist = True
	if exist == False:
		booksPerGenre.append([book, 1])
choice = 0
for i in range(len(booksPerGenre) - 1):
	for j in range(len(booksPerGenre) - 1 - i):
		choice = choice + booksPerGenre[i][1] * booksPerGenre[j + i + 1][1]
print(choice)


(n, m) = map(int, input().split())
books = list(map(int, input().split()))
cBooks = [0] * m
for book in books:
	cBooks[book - 1] += 1
answer = 0
for i in range(m):
	for j in range(i + 1, m, 1):
		answer += cBooks[i] * cBooks[j]
print(answer)


(n, m) = [int(x) for x in input().split()]
ans = 0
t = n
d = {}
x = list(map(int, input().split()))
for e in x:
	if e in d:
		d[e] += 1
	else:
		d[e] = 1
for i in d:
	t -= d[i]
	ans += t * d[i]
print(ans)


(n, m) = map(int, input().split())
l = [0 for i in range(m + 1)]
ol = [0] + list(map(int, input().split()))
for i in ol:
	l[i] += 1
ans = 0
for i in range(1, m):
	for j in range(i + 1, m + 1):
		ans += l[i] * l[j]
print(ans)


(n, m) = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
a = [a.count(i + 1) for i in range(m)]
c = 0
for i in range(m - 1):
	c += a[i] * sum(a[i + 1:])
print(c)


(n, m) = map(int, input().split())
l = [int(x) for x in input().split()]
d = {}
for x in l:
	if x not in d:
		d[x] = 1
	else:
		d[x] += 1
ans = n * (n - 1) // 2
for x in d:
	ans -= d[x] * (d[x] - 1) // 2
print(ans)


(n, m) = list(map(int, input().split()))
A = list(map(int, input().split()))
count = 1
D = {}
for val in A:
	if val not in D:
		D[val] = 1
	else:
		D[val] += 1
	count += 1
Ans = n * (n - 1) // 2
for val in D:
	x = D[val]
	x = x * (x - 1) // 2
	Ans -= x
print(Ans)


(n, m) = map(int, input().split())
l = list(map(int, input().split()))
d = {}
ans = 0
for x in l:
	d[x] = d.get(x, 0) + 1
for x in set(l):
	ans += (sum(d.values()) - d[x]) * d[x]
print(ans // 2)


(n, m) = map(int, input().split())
ip = list(map(int, input().split()))
count = 0
t = 1
c = []
ans = 0
while count < n:
	c.append(ip.count(t))
	count += ip.count(t)
	t += 1
for i in range(m):
	for j in range(i + 1, m):
		ans += c[i] * c[j]
print(ans)


from collections import Counter
(n, m) = list(map(int, input().split()))
c = Counter(list(map(int, input().split())))
a = list(c.keys())
print(sum((c[a[i]] * c[a[j]] for i in range(len(a) - 1) for j in range(i + 1, len(a)))))


(n, m) = input().split()
(n, m) = (int(n), int(m))
l = [0] * m
s = input().split()
for i in range(n):
	l[int(s[i]) - 1] += 1
r = 0
for i in range(m):
	r += l[i]
(p, q) = (0, 0)
for i in range(m):
	p += l[i]
	q += l[i] * (r - p)
print(q)


(n, m) = map(int, input().split())
a = list(map(int, input().split()))
ans = 0
t = n
for i in range(1, m):
	cai = a.count(i)
	ans += cai * (t - cai)
	t -= cai
print(ans)


tmp = input()
tmp = tmp.split()
n = int(tmp[0])
m = int(tmp[1])
cnt = [0] * m
tmp = input()
tmp = tmp.split()
for x in tmp:
	cnt[int(x) - 1] += 1
rez = 0
for i in range(0, m):
	for j in range(i + 1, m):
		rez += cnt[i] * cnt[j]
print(rez)


(n, m) = map(int, input().split())
a = list(map(int, input().split()))
v = [0] * (m + 1)
for i in a:
	v[i] += 1
an = n * (n - 1) // 2
for i in v:
	an -= i * (i - 1) // 2
print(an)


(n, m) = map(int, input().split())
a = list(map(int, input().split()))
count = [0] * 15
for book in a:
	count[book] += 1
sum = 0
for i in range(1, m):
	for j in range(i + 1, m + 1):
		sum += count[i] * count[j]
print(sum)


def func(f, m):
	i = 0
	j = 0
	ans = 0
	while i < m - 1:
		j = i + 1
		while j < m:
			ans += f[i] * f[j]
			j += 1
		i += 1
	return ans
(n, m) = map(int, input().split())
a = list(map(int, input().split()))
index = 0
x = 0
f = [0]
f = f * 10
while n > 0:
	f[a[index] - 1] += 1
	index += 1
	n -= 1
x = func(f, m)
print(x)


(n, m) = map(int, input().split())
a = list(map(int, input().split()))
d = {i: 0 for i in range(1, m + 1)}
for num in a:
	d[num] += 1
n_sum = 0
for i in range(1, m + 1):
	n_sum += d[i] * (d[i] - 1) // 2
print(int(n * (n - 1) / 2 - n_sum))


from functools import *
(n, m) = map(int, input().split())
cnt = [0] * (m + 1)
a = list(map(int, input().split()))
for x in a:
	cnt[x] += 1
print(reduce(lambda res, x: res + x * (n - x), cnt, 0) // 2)


(n, m) = map(int, input().strip().split())
d = {}
for i in map(int, input().strip().split()):
	d[i] = d.get(i, 0) + 1
ans = 0
for (i, v1) in enumerate(list(d.values())):
	for v2 in list(d.values())[i + 1:]:
		ans += v1 * v2
print(ans)


from collections import Counter
(n, m) = map(int, input().split())
a = list(map(int, input().split()))
c = Counter(a)
l = c.values()
s = sum(l)
ans = 0
for i in l:
	s -= i
	ans += s * i
print(ans)


read = lambda : list(map(int, input().split()))
(n, m) = read()
a = list(read())
p = [0] * 20
for i in a:
	p[i] += 1
cnt = n * (n - 1) // 2
for i in p:
	cnt -= i * (i - 1) // 2
print(cnt)


[n, m] = list(map(int, input().rstrip().split()))
a = list(map(int, input().rstrip().split()))
count = [0 for i in range(m)]
for i in range(n):
	count[a[i] - 1] += 1
quad = [count[i] ** 2 for i in range(m)]
somma2 = sum(count) ** 2
squad = sum(quad)
ans = (somma2 - squad) // 2
print(ans)


(n, m) = map(int, input().split())
arr = list(map(int, input().split()))
occ = [0] * m
for v in arr:
	occ[v - 1] += 1
ans = 0
for i in range(m):
	for j in range(i + 1, m):
		ans += occ[i] * occ[j]
print(ans)


(b, g) = map(int, input().split())
a = list(map(int, input().split()))
cnt = 0
ten = [0] * 11
for i in range(b):
	ten[a[i]] += 1
for i in range(1, g):
	for j in range(i + 1, g + 1):
		cnt += ten[i] * ten[j]
print(cnt)


(n, m) = map(int, input().split())
s1 = list(map(int, input().split()))
a = [0] * m
for i in range(n):
	a[s1[i] - 1] += 1
kol = 0
for i in range(m - 1):
	for j in range(i + 1, m):
		kol = kol + a[i] * a[j]
print(kol)


import collections
nm = list(map(int, input().split()))
m = nm[1]
A = list(map(int, input().split()))
counter = collections.Counter(A)
B = list(counter.values())
res = 0
for i in range(m):
	for j in range(i + 1, m, 1):
		res += B[i] * B[j]
print(res)


(n, m) = map(int, input().split())
array = [i for i in map(int, input().split())]
listofzeros = [0] * m
count = 0
my_dict = dict()
for num in array:
	if num in my_dict:
		my_dict[num] += 1
	else:
		my_dict[num] = 1
for (key, value) in my_dict.items():
	if value > 1:
		count += int(value * (value - 1) / 2)
print(int(n * (n - 1) / 2 - count))


duplicated_keys = {}

def calculate_chinh_hop_of_2(number_books):
	return int(number_books * (number_books - 1) / 2)
(number_books, number_genders) = list(map(int, input().split()))
number_data = list(map(int, input().split()))
number_of_choosing_books = calculate_chinh_hop_of_2(number_books)
for book in number_data:
	if book not in duplicated_keys:
		duplicated_keys[book] = 1
	else:
		duplicated_keys[book] += 1
for value in duplicated_keys.values():
	number_of_choosing_books -= calculate_chinh_hop_of_2(value)
print(number_of_choosing_books)


first = input()
first = list(map(int, first.split()))
n = first[0]
m = first[1]
second = input()
books = list(map(int, second.split()))
books.sort()
options = 0
for genre in range(1, m + 1):
	freq = books.count(genre)
	books = list(filter(genre.__ne__, books))
	count = freq * len(books)
	options += count
print(options)


(n, m) = map(int, input().split())
res = [0] * m
count = 0
data = list(map(int, input().split()))
for i in data:
	res[i - 1] += 1
Sum = n
for i in range(len(res)):
	Sum -= res[i]
	count += res[i] * Sum
print(count)


inputLineOne = [int(n) for n in input().split()]
nbooks = inputLineOne[0]
ngenres = inputLineOne[1]
genres = [int(n) for n in input().split()]
genreTable = [0 for i in range(ngenres)]
for b in genres:
	genreTable[b - 1] += 1
N = 0
for i in range(ngenres):
	for j in range(i + 1, ngenres):
		N += genreTable[i] * genreTable[j]
print(N)


(n, m) = map(int, input().split())
books = [int(x) for x in input().split()]
total = n * (n - 1) / 2
genres = [0] * m
for book in books:
	genres[book - 1] += 1
for genre in genres:
	total -= genre * (genre - 1) / 2
print(int(total))


import sys
from bisect import bisect_right as rb
from collections import deque
from queue import PriorityQueue
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()
mod = 10 ** 9 + 7
(n, m) = il()
a = il()
d = [0 for i in range(m + 1)]
for i in a:
	d[i] += 1
ans = 0
for i in d:
	ans += i * (n - i)
print(ans // 2)


(n, m) = [int(x) for x in input().split()]
cnt = [0 for x in range(100)]
for x in [int(x) for x in input().split()]:
	cnt[x] += 1
ans = 0
for i in range(1, 11):
	ans += (sum(cnt) - cnt[i]) * cnt[i]
print(ans // 2)


intro = input()
variables = intro.split(' ')
books = variables[0]
genres = variables[1]
choices = 0
bookGenreDict = {}
genreLine = input()
for genre in genreLine.split(' '):
	if genre in bookGenreDict:
		bookGenreDict[genre] += 1
	else:
		bookGenreDict[genre] = 1
bookGenreList = []
for genre in bookGenreDict:
	bookGenreList.append(bookGenreDict[genre])
choices = 0
for book1 in range(len(bookGenreList) - 1):
	for book2 in range(book1 + 1, len(bookGenreList)):
		choices += bookGenreList[book1] * bookGenreList[book2]
print(choices)


(n, g) = map(int, input().split())
a = list(map(int, input().split()))
gn = [0] * g
for i in range(g):
	c = a.count(i + 1)
	gn[i] = c
ans = 0
for i in range(g):
	for j in range(i + 1, g):
		ans += gn[i] * gn[j]
print(ans)


(n, m) = map(int, input().split())
v = list(map(int, input().split()))
cnt = [0 for i in range(0, m + 1)]
for x in v:
	cnt[x] += 1
sol = n * (n - 1) // 2
for x in cnt:
	sol -= x * (x - 1) // 2
print(sol)


(n, m) = map(int, input().split())
arr = list(map(int, input().split()))
ans = 0
count = [0] * m
for i in range(n):
	count[arr[i] - 1] += 1
for i in range(m):
	ans += count[i] * (n - count[i])
print(ans // 2)


(n, m) = map(int, input().split())
b = [0] * m
sum = 0
s = list(map(int, input().split()))
for i in range(n):
	b[s[i] - 1] += 1
for i in range(1, m):
	for j in range(0, i):
		sum += b[j] * b[i]
print(sum)


import sys
input = sys.stdin.readline

def main():
	(n, m) = map(int, input().split())
	l = list(map(int, input().split()))
	q = [0] * (m + 1)
	for i in range(n):
		q[l[i]] += 1
	r = 0
	for i in range(1, m + 1):
		k = q[i]
		n -= k
		r += n * k
	print(r)
main()


def inp():
	return map(int, input().split())
(n, m) = inp()
a = list(inp())
b = [0] * m
for i in range(n):
	b[a[i] - 1] += 1
count = 0
for i in range(0, m):
	temp = 0
	for j in range(i + 1, m):
		temp += b[j]
	count += b[i] * temp
print(count)


(n, m) = map(int, input().split())
a = list(map(int, input().split()))
tmp1 = int((n - 1) * n / 2)
b = {}
for item in a:
	b[item] = b.get(item, 0) + 1
tmp2 = 0
for item in b.values():
	if item > 1:
		tmp2 += int(item * (item - 1) / 2)
print(tmp1 - tmp2)


import math
(n, m) = map(int, input().split())
numbers = [0 for i in range(m)]
for item in map(int, input().split()):
	numbers[item - 1] += 1
ans = n * (n - 1) / 2
for item in numbers:
	ans -= item * (item - 1) / 2
print(int(ans))


(n, m) = map(int, input().split())
a = list(map(int, input().split(' ')))
o = 0
c = 0
t = []
sm = n
for i in range(m + 1):
	t.append(0)
for i in range(n):
	t[a[i]] += 1
for i in range(1, m + 1):
	sm -= t[i]
	o += t[i] * sm
print(o)


import os, sys
from io import IOBase, BytesIO
py2 = round(0.5)
if py2:
	from future_builtins import ascii, filter, hex, map, oct, zip
	range = xrange
BUFSIZE = 8192

class FastIO(BytesIO):
	newlines = 0

	def __init__(self, file):
		self._file = file
		self._fd = file.fileno()
		self.writable = 'x' in file.mode or 'w' in file.mode
		self.write = super(FastIO, self).write if self.writable else None

	def _fill(self):
		s = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
		self.seek((self.tell(), self.seek(0, 2), super(FastIO, self).write(s))[0])
		return s

	def read(self):
		while self._fill():
			pass
		return super(FastIO, self).read()

	def readline(self):
		while self.newlines == 0:
			s = self._fill()
			self.newlines = s.count(b'\n') + (not s)
		self.newlines -= 1
		return super(FastIO, self).readline()

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

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		if py2:
			self.write = self.buffer.write
			self.read = self.buffer.read
			self.readline = self.buffer.readline
		else:
			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')
import sys

class ostream:

	def __lshift__(self, a):
		sys.stdout.write(str(a))
		return self
cout = ostream()
endl = '\n'

def solve():
	(n, m) = map(int, input().split())
	arr = map(int, input().split())
	freq = {x: 0 for x in range(1, 11)}
	for i in arr:
		freq[i] += 1
	res = 0
	for i in range(1, 11):
		for j in range(i + 1, 11):
			res += freq[i] * freq[j]
	cout << res << endl

def main():
	solve()
main()


(n, m) = map(int, input().split())
a = list(map(int, input().split()))
total = 0
type_list = [0] * m
for i in range(n):
	type_list[a[i] - 1] += 1
for j in range(m - 1):
	for k in range(j + 1, m):
		total += type_list[j] * type_list[k]
print(total)


(n, m) = input().split(' ')
arr = input().strip().split(' ')
hsh = [0 for i in range(0, 11)]
ans = [0 for i in range(0, 11)]
for i in arr:
	hsh[int(i)] += 1
m = int(m)
for i in range(1, int(m)):
	for j in range(i + 1, m + 1):
		ans[i] += hsh[i] * hsh[j]
fnl = 0
for i in range(1, m + 1):
	fnl += ans[i]
print(fnl)


from collections import Counter
(N, M) = map(int, input().split())
A = list(map(int, input().split()))
cnt = list(Counter(A).values())
l = len(cnt)
ruiseki = [0] * (l + 1)
for i in range(l):
	ruiseki[i + 1] = ruiseki[i] + cnt[i]
ans = 0
for i in range(l):
	ans += cnt[i] * (ruiseki[l] - ruiseki[i + 1])
print(ans)


(n, m) = [int(x) for x in input().split()]
s = [int(x) for x in input().split()]
sm = 0
genres = [0] * (m + 1)
for item in s:
	genres[item] += 1
for i in range(1, m + 1):
	for j in range(i + 1, m + 1):
		sm += genres[j] * genres[i]
print(sm)


from functools import reduce
from operator import *
from math import *
from sys import *
from string import *
from collections import *
setrecursionlimit(10 ** 7)
dX = [-1, 1, 0, 0, -1, 1, -1, 1]
dY = [0, 0, -1, 1, 1, -1, -1, 1]
RI = lambda : list(map(int, input().split()))
RS = lambda : input().rstrip().split()
(n, m) = RI()
cnt = [0] * (m + 1)
a = RI()
for i in a:
	cnt[i] += 1
ans = 0
t = sum(cnt)
for i in cnt:
	t -= i
	ans += i * t
print(ans)


(i, v) = map(int, input().split())
l = list(map(int, input().split()))
m = {}
for x in set(l):
	m[x] = l.count(x)
t = 0
for x in range(i):
	m[l[x]] -= 1
	t += sum(m.values()) - m[l[x]]
print(t)


def read_ints():
	return list(map(int, input().split()))
(bookCount, topicCount) = read_ints()
books = {}
for book in read_ints():
	books[book] = books.get(book, 0) + 1
result = 0
i = 0
for curBooks in books.values():
	result += curBooks * (bookCount - curBooks)
	bookCount -= curBooks
	i += 1
print(result)


n = int(input().split()[0])
total = n * (n - 1) / 2
books = input().split()
for b in set(books):
	count = books.count(b)
	if count > 1:
		total -= count * (count - 1) / 2
print(int(total))


(n, m) = map(int, input().split())
l = list(map(int, input().split()))
d = {}
for i in set(l):
	d[i] = 0
c = 0
d[l[-1]] = 1
for i in range(n - 2, -1, -1):
	f = d[l[i]]
	if f == 0:
		d[l[i]] = 1
	else:
		d[l[i]] = d[l[i]] + 1
	c = c + n - (i + 1) - f
print(c)


import sys
from collections import Counter

def solve(nb_books, nb_genres, books):
	counter = Counter(books)
	nb_possibilities = 0
	nb_seen = 0
	for (genre, count) in counter.items():
		nb_remaining_books = max(0, nb_books - nb_seen - count)
		nb_possibilities += count * nb_remaining_books
		nb_seen += count
	return nb_possibilities
assert solve(4, 3, [2, 1, 3, 1]) == 5
assert solve(7, 4, [4, 2, 3, 1, 2, 4, 3]) == 18
(nb_books, nb_genres) = map(int, input().strip().split(' '))
books = input().strip().split(' ')
print(solve(nb_books, nb_genres, books))


def dumdumjake(n, m, a):
	w = 0
	v = [0] * max(a)
	if n - m != 0:
		for i in a:
			v[i - 1] += 1
	for i in v:
		w += i * (i - 1) // 2
	return n * (n - 1) // 2 - w
(n, m) = input().strip().split()
a = input().strip().split()
a = list(map(int, a))
print(dumdumjake(int(n), int(m), a))


from collections import Counter
(n, m) = map(int, input().split())
li = list(map(int, input().split()))
count = dict(Counter(li))
sum = n * (n - 1) / 2
for (k, v) in count.items():
	if v > 1:
		sum -= v * (v - 1) / 2
print(int(sum))


try:
	while True:
		(n, m) = map(int, input().split())
		a = [0] * m
		for x in map(int, input().split()):
			a[x - 1] += 1
		result = 0
		for (i, x) in enumerate(a):
			for y in a[i + 1:]:
				result += x * y
		print(result)
except EOFError:
	pass


(n, m) = [int(i) for i in input().split()]
genres = [0 for i in range(m)]
books = [int(i) for i in input().split()]
for book in books:
	genres[book - 1] += 1
a = 0
for i in range(m):
	for j in range(i + 1, m):
		a += genres[i] * genres[j]
print(a)


(n, m) = map(int, input().split())
counter = 0
dic = {}
for i in list(map(int, input().split())):
	if i not in dic:
		dic[i] = 1
	else:
		dic[i] += 1
for i in dic:
	s = 0
	for y in dic:
		if y != i and i > y:
			s += dic[y]
	counter += dic[i] * s
print(counter)


import time
(n, m) = (int(i) for i in input().split())
a = [int(i) for i in input().split()]
start = time.time()
d = {}
ans = 0
for i in range(m):
	d[i] = 0
for i in a:
	d[i - 1] += 1
k = n
for i in range(m - 1):
	k -= d[i]
	ans += d[i] * k
print(ans)
finish = time.time()


(n, m) = str(input()).split()
(n, m) = (int(n), int(m))
line = str(input()).split()
line = [int(it) for it in line]
note = [0] * m
for it in line:
	note[it - 1] += 1
num = 0
for i in range(m - 1):
	for j in range(i + 1, m):
		num += note[i] * note[j]
print(num)


def inp():
	return map(int, input().split(' '))
(n, m) = inp()
a = inp()
count = [0] * m
answer = 0
for x in a:
	count[x - 1] += 1
for i in range(0, m):
	x = count[i]
	answer = answer + (n - x) * x
print(answer // 2)


(n, m) = map(int, input().split())
a = list(map(int, input().split()))
s = set(a)
tong = sum(range(n))
tong1 = 0
for i in s:
	z = a.count(i)
	if z > 1:
		g = sum(range(z))
		tong1 += g
print(tong - tong1)


(nBooks, mGenres) = map(int, input().split())
aList = list(map(int, input().split()))
bookList = [0] * nBooks
count = [0] * (mGenres + 1)
ans = 0
for x in aList:
	count[x] += 1
for x in count:
	ans += (nBooks - x) * x
print(ans // 2)


import sys
import string
from collections import Counter, defaultdict
from math import fsum, sqrt, gcd, ceil, factorial
from operator import *
from itertools import accumulate
inf = float('inf')
flush = lambda : sys.stdout.flush
comb = lambda x, y: factorial(x) // factorial(y) // factorial(x - y)
ip = lambda : input()
ii = lambda : int(input())
r = lambda : map(int, input().split())
rr = lambda : list(r())
(n, k) = r()
arr = rr()
arr = Counter(arr)
c = 0
for i in arr.values():
	c += i * (n - i)
print(c // 2)


(N, M) = map(int, input().split())
A = list(map(int, input().split()))
D = [0 for _ in range(M)]
for i in range(N):
	D[A[i] - 1] += 1
res = 0
for i in range(M - 1):
	for j in range(i + 1, M):
		res += D[i] * D[j]
print(res)


from __future__ import print_function
import sys
(n, m) = map(int, input().split())
M = [0 for i in range(0, m)]
A = map(int, input().split())
for a in A:
	M[a - 1] = M[a - 1] + 1
total = 0
for x in M:
	total = total + x * (n - x)
total = int(total / 2)
print(total)


(n, m) = map(int, input().split())
genres = list(map(int, input().split()))
q = [0] * m
for i in range(n):
	q[genres[i] - 1] += 1
print(sum((q[i] * q[j] for i in range(m) for j in range(i + 1, m))))


(n, m) = list(map(int, input().split()))
a = list(map(int, input().split()))
mp = [0] * m
cnt = 0
for x in a:
	mp[x - 1] += 1
for x in range(m + 1):
	for t in range(x + 1, m, 1):
		cnt += mp[x] * mp[t]
print(cnt)


(n, m) = map(int, input().split())
a = list(map(int, input().split()))
d = [0 for i in range(m)]
for i in range(n):
	d[a[i] - 1] += 1
x = 0
for i in range(m):
	if d[i] > 1:
		p = d[i] * (d[i] - 1)
		x += p // 2
y = n * (n - 1) // 2
print(y - x)


a = input()
n = int(a.split()[0])
m = int(a.split()[1])
k = n * (n - 1) / 2
b = list(map(int, input().split()))
l = [b.count(x) for x in set(b)]
for i in l:
	if i > 1:
		p = i * (i - 1) / 2
		k = k - p
print(int(k))


(n, m) = map(int, input().split())
ans = 0
l = list(map(int, input().split()))
d = [0 for i in range(m)]
for i in l:
	d[i - 1] += 1
val = [i for i in d]
for i in range(len(val) - 2, -1, -1):
	val[i] += val[i + 1]
for i in range(m - 1):
	ans += d[i] * val[i + 1]
print(ans)


a = input()
a = a.split()
b = input()
b = b.split()
a = list(map(lambda x: int(x), a))
b = list(map(lambda x: int(x), b))
total_case = a[0] * (a[0] - 1) / 2
genre_list = {}
wrong_cases = 0
for i in b:
	if i not in genre_list:
		genre_list[i] = 1
	else:
		genre_list[i] += 1
for i in genre_list:
	wrong_cases += genre_list[i] * (genre_list[i] - 1) / 2
print(int(total_case - wrong_cases))


(books, genres) = map(int, input().split())
array = sorted([int(x) for x in input().split()])
books_compared = list()
sample_point = array[0]
counter = 0
different_ways = 0
for i in range(books):
	if sample_point == array[i]:
		counter = counter + 1
	elif books - counter > 0:
		different_ways += (books - counter) * counter
		books = books - counter
		counter = 1
	sample_point = array[i]
print(different_ways)


(n, m) = map(int, input().split())
a = list(map(int, input().split()))
cnt = [0] * (10 + 1)
for x in a:
	cnt[x] += 1
res = 0
for i in range(1, m):
	for j in range(i + 1, m + 1):
		res += cnt[i] * cnt[j]
print(res)


n = [int(i) for i in input().split(' ')]
d = {}
for i in input().split(' '):
	d.update({int(i): d.get(int(i), 0) + 1})
k = 0
for i in d:
	k += d[i] * (n[0] - d[i])
	n[0] -= d[i]
print(k)


(n, m) = map(int, input().split())
a = [int(i) for i in input().split()]
b = [0] * m
for i in a:
	b[i - 1] += 1
sum = b[0]
ans = 0
for i in range(1, len(b)):
	ans += sum * b[i]
	sum += b[i]
print(ans)


(n, m) = map(int, input().split())
a = input().split()
result = 0
for i in range(m):
	count = a.count(str(i + 1))
	result += count * (n - count)
print(result // 2)


def inp():
	return map(int, input().split())
(m, n) = inp()
a = inp()
count = n * [0]
cnt = 0
for x in a:
	count[x - 1] += 1
for i in range(n - 1):
	for j in range(i + 1, n):
		cnt += count[i] * count[j]
print(cnt)


(n, m) = [int(x) for x in input().split()]
a = [int(x) - 1 for x in input().split()]
b = [0] * 10
ans = 0
for x in a:
	b[x] += 1
for i in range(10):
	if b[i] != 0:
		x = b[i]
		for j in range(i + 1, 10):
			ans += x * b[j]
print(ans)


from collections import Counter
I = lambda : map(int, input().split())
(n, _) = I()
print(sum((v * (n - v) for v in Counter(I()).values())) // 2)


from functools import cmp_to_key
from collections import deque, Counter
from heapq import heappush, heappop
from math import log, ceil
import sys
import 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')
if sys.version_info[0] < 3:
	(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()

def inp():
	return sys.stdin.readline().rstrip('\r\n')

def ii():
	return int(inp())

def si():
	return str(inp())

def li(lag=0):
	l = list(map(int, inp().split()))
	if lag != 0:
		for i in range(len(l)):
			l[i] += lag
	return l

def mi(lag=0):
	matrix = list()
	for i in range(n):
		matrix.append(li(lag))
	return matrix

def lsi():
	return list(map(str, inp().split()))

def print_list(lista, space=' '):
	print(space.join(map(str, lista)))

def bisect_left(a, x):
	left = 0
	right = len(a)
	while left < right:
		mid = (left + right) // 2
		if a[mid] < x:
			left = mid + 1
		else:
			right = mid
	return left

def bisect_right(a, x):
	left = 0
	right = len(a)
	while left < right:
		mid = (left + right) // 2
		if a[mid] > x:
			right = mid
		else:
			left = mid + 1
	return left

def bisect_elements(a, x):
	return bisect_right(a, x) - bisect_left(a, x)
MOD = 10 ** 9 + 7
maxN = 5
FACT = [0] * maxN
INV_FACT = [0] * maxN

def add(x, y):
	return (x + y) % MOD

def multiply(x, y):
	return x * y % MOD

def power(x, y):
	if y == 0:
		return 1
	elif y % 2:
		return multiply(x, power(x, y - 1))
	else:
		a = power(x, y // 2)
		return multiply(a, a)

def inverse(x):
	return power(x, MOD - 2)

def divide(x, y):
	return multiply(x, inverse(y))

def allFactorials():
	FACT[0] = 1
	for i in range(1, maxN):
		FACT[i] = multiply(i, FACT[i - 1])

def inverseFactorials():
	n = len(INV_FACT)
	INV_FACT[n - 1] = inverse(FACT[n - 1])
	for i in range(n - 2, -1, -1):
		INV_FACT[i] = multiply(INV_FACT[i + 1], i + 1)

def coeffBinom(n, k):
	if n < k:
		return 0
	return multiply(FACT[n], multiply(INV_FACT[k], INV_FACT[n - k]))

def create_graph(n, m, undirected=1, unweighted=1):
	graph = [[] for i in range(n)]
	if unweighted:
		for i in range(m):
			[x, y] = li(lag=-1)
			graph[x].append(y)
			if undirected:
				graph[y].append(x)
	else:
		for i in range(m):
			[x, y, w] = li(lag=-1)
			w += 1
			graph[x].append([y, w])
			if undirected:
				graph[y].append([x, w])
	return graph

def create_tree(n, unweighted=1):
	children = [[] for i in range(n)]
	if unweighted:
		for i in range(n - 1):
			[x, y] = li(lag=-1)
			children[x].append(y)
			children[y].append(x)
	else:
		for i in range(n - 1):
			[x, y, w] = li(lag=-1)
			w += 1
			children[x].append([y, w])
			children[y].append([x, w])
	return children

def dist(tree, n, A, B=-1):
	s = [[A, 0]]
	(massimo, massimo_nodo) = (0, 0)
	distanza = -1
	v = [-1] * n
	while s:
		(el, dis) = s.pop()
		if dis > massimo:
			massimo = dis
			massimo_nodo = el
		if el == B:
			distanza = dis
		for child in tree[el]:
			if v[child] == -1:
				v[child] = 1
				s.append([child, dis + 1])
	return (massimo, massimo_nodo, distanza)

def diameter(tree):
	(_, foglia, _) = dist(tree, n, 0)
	(diam, _, _) = dist(tree, n, foglia)
	return diam

def dfs(graph, n, A):
	v = [-1] * n
	s = [[A, 0]]
	v[A] = 0
	while s:
		(el, dis) = s.pop()
		for child in graph[el]:
			if v[child] == -1:
				v[child] = dis + 1
				s.append([child, dis + 1])
	return v

def bfs(graph, n, A):
	v = [-1] * n
	s = deque()
	s.append([A, 0])
	v[A] = 0
	while s:
		(el, dis) = s.popleft()
		for child in graph[el]:
			if v[child] == -1:
				v[child] = dis + 1
				s.append([child, dis + 1])
	return v

def parents_children_root_unrooted_tree(tree, n, root=0):
	q = deque()
	visited = [0] * n
	parent = [-1] * n
	children = [[] for i in range(n)]
	q.append(root)
	while q:
		all_done = 1
		visited[q[0]] = 1
		for child in tree[q[0]]:
			if not visited[child]:
				all_done = 0
				q.appendleft(child)
		if all_done:
			for child in tree[q[0]]:
				if parent[child] == -1:
					parent[q[0]] = child
					children[child].append(q[0])
			q.popleft()
	return (parent, children)

def all_longest_path_passing_from_node(parent, children, n):
	q = deque()
	visited = [len(children[i]) for i in range(n)]
	downwards = [[0, 0] for i in range(n)]
	upward = [1] * n
	longest_path = [1] * n
	for i in range(n):
		if not visited[i]:
			q.append(i)
			downwards[i] = [1, 0]
	while q:
		node = q.popleft()
		if parent[node] != -1:
			visited[parent[node]] -= 1
			if not visited[parent[node]]:
				q.append(parent[node])
		else:
			root = node
		for child in children[node]:
			downwards[node] = sorted([downwards[node][0], downwards[node][1], downwards[child][0] + 1], reverse=True)[0:2]
	s = [node]
	while s:
		node = s.pop()
		if parent[node] != -1:
			if downwards[parent[node]][0] == downwards[node][0] + 1:
				upward[node] = 1 + max(upward[parent[node]], downwards[parent[node]][1])
			else:
				upward[node] = 1 + max(upward[parent[node]], downwards[parent[node]][0])
		longest_path[node] = downwards[node][0] + downwards[node][1] + upward[node] - min([downwards[node][0], downwards[node][1], upward[node]]) - 1
		for child in children[node]:
			s.append(child)
	return longest_path

def bin(n):
	return n * (n - 1) // 2
(n, m) = li()
a = li()
res = bin(n)
c = [0] * (m + 1)
for el in a:
	c[el] += 1
for el in range(m + 1):
	res -= bin(c[el])
print(res)


(n, m) = [int(i) for i in input().split()]
lst = [0 for i in range(m)]
inp = [int(i) for i in input().split()]
for i in inp:
	lst[i - 1] += 1
lst = [i * (i - 1) // 2 for i in lst if i > 1]
print(n * (n - 1) // 2 - sum(lst))


(n, m) = [int(i) for i in input().split()]
A = [int(i) for i in input().split()]
m_arr = [0 for i in range(m + 1)]
for i in A:
	m_arr[i] += 1
A = m_arr[1:]
prefix_arr = []
curr_sum = 0
for i in A:
	curr_sum += i
	prefix_arr.append(curr_sum)
total_val = 0
for i in range(len(prefix_arr) - 1):
	total_val += A[i] * (prefix_arr[-1] - prefix_arr[i])
print(total_val)


from collections import Counter
import functools

def main():
	(n, m) = map(int, input().split(' '))
	arr = [int(i) for i in input().split(' ')]
	mp = Counter()
	for i in arr:
		mp[i] += 1
	res = 0
	for count in mp.values():
		res += count * (n - count)
		n -= count
	print(res)
main()


(n, m) = map(int, input().split())
a = list(map(int, input().split()))
s = [0] * m
for i in a:
	s[i - 1] += 1
k = 0
for i in s:
	k += (n - i) * i
print(k // 2)


(n, m) = map(int, input().split())
a = list(map(int, input().split()))
z = 0
for i in range(1, m + 1):
	f = a.count(i)
	z += f * (f - 1) // 2
k = len(a) * (len(a) - 1) // 2 - z
print(k)


(n, m) = [int(x) for x in input().split()]
books = [int(x) for x in input().split()]
D = {i: 0 for i in range(1, m + 1)}
for i in range(n):
	D[books[i]] += 1
res = 0
for k in D:
	res += D[k] * (n - D[k])
print(res // 2)


(n, m) = map(int, input().split())
a = [int(s) for s in input().split()]
b = [0] * m
for i in range(n):
	b[a[i] - 1] += 1
sum = n * (n - 1) // 2
for i in range(m):
	sum -= max(0, b[i] * (b[i] - 1) // 2)
print(sum)


(n, m) = map(int, input().split())
arr = []
for i in range(m + 1):
	arr.append(0)
for x in input().split():
	x = int(x)
	arr[x] += 1
l = len(arr)
cnt = 0
for i in range(1, l):
	for j in range(i + 1, l):
		cnt += arr[i] * arr[j]
print(cnt)


(n, m) = input().split()
m = int(m)
n = int(n)
ls = input()
ls = list(map(int, ls.split()))
arr = [0] * (m + 1)
for x in range(n):
	y = ls[x]
	arr[y] += 1
su = 0
for x in range(1, m + 1):
	ss = 0
	pf = arr[x]
	y = x + 1
	while y <= m:
		ss += arr[y]
		y = y + 1
	su = su + ss * pf
print(su)


(n, m) = input().split()
n = int(n)
ms = [int(x) for x in input().split()]
st = set(ms)
c = 0
for i in st:
	k = ms.count(i)
	n -= k
	c += n * k
print(c)


(n, m) = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
b = list(set(a))
num = 0
for i in b:
	for t in b:
		if i != t:
			num += a.count(i) * a.count(t)
print(num // 2)


(n, m) = [int(x) for x in input().split()]
cnt = [0 for x in range(m)]
for x in input().split():
	num = int(x) - 1
	cnt[num] += 1
ans = 0
for i in range(m):
	for j in range(i):
		ans = ans + cnt[i] * cnt[j]
print(ans)


import sys
from collections import Counter

def get_array():
	return list(map(int, sys.stdin.readline().split()))

def get_ints():
	return map(int, sys.stdin.readline().split())

def input():
	return sys.stdin.readline().strip('\n')
(n, m) = get_ints()
l = get_array()
d = Counter(l)
cal = 0
for i in d:
	if d[i] > 1:
		cal += d[i] * (d[i] - 1) // 2
print(n * (n - 1) // 2 - cal)


(n, m) = map(int, input().split())
a = [int(x) for x in input().split()]
c = [0] * 11
ans = 0
for i in range(n):
	c[a[i]] += 1
for i in range(1, m):
	for j in range(i + 1, m + 1):
		ans += c[i] * c[j]
print(ans)


nurray = input().split()
A = list(input().split())
A = [int(x) for x in A]
dem = 0
for i in range(1, int(nurray[1]) + 1):
	dt = A.count(i)
	dem += 0.5 * dt * (dt - 1)
ct = 0.5 * (int(nurray[0]) * (int(nurray[0]) - 1)) - dem
print(int(ct))


import sys
from collections import Counter

def number_of_ways(books):
	n = len(books)
	c = Counter(books)
	return sum((v * (n - v) for (_, v) in c.items())) // 2
(n, m) = [int(x) for x in sys.stdin.readline().strip().split()]
books = [int(x) for x in sys.stdin.readline().strip().split()]
sys.stdout.write('{}\n'.format(number_of_ways(books)))


from collections import Counter

def solve():
	(N, M) = map(int, input().split())
	gen = list(map(int, input().split()))
	cnt = Counter(gen)
	total = 0
	for (gen1, cnt1) in cnt.items():
		for (gen2, cnt2) in cnt.items():
			if gen1 == gen2:
				continue
			total += cnt1 * cnt2
	print(total // 2)
solve()


from collections import Counter

def possibilities(C, m, n):
	cnt = Counter(C)
	prod = 0
	M = [v for (_, v) in cnt.items()]
	for i in range(len(M) - 1):
		for j in M[i + 1:]:
			prod += M[i] * j
	return prod
(n, m) = input().split(' ')
(n, m) = (int(n), int(m))
C = input().split(' ')
C = [int(c) for c in C]
print(possibilities(C, m, n))


from collections import Counter
from itertools import combinations
(n, m) = map(int, input().split())
genres = Counter(map(int, input().split()))
count = 0
for (a, b) in combinations(range(1, m + 1), 2):
	count += genres[a] * genres[b]
print(count)


(n, m) = list(map(int, input().strip().split()))
a = list(map(int, input().strip().split()))
d = dict()
for i in a:
	if i in d.keys():
		d[i] += 1
	else:
		d[i] = 1
v = d.values()
s = 0
sq = 0
for i in v:
	s += i
	sq += i ** 2
print((s ** 2 - sq) // 2)


from operator import *
from functools import *
(B, G) = map(int, input().split())
A = list(map(int, input().split()))
Genres = [0] * G
for a in A:
	Genres[a - 1] += 1

def nCr(n, r):
	r = min(r, n - r)
	num = reduce(mul, range(n, n - r, -1), 1)
	den = reduce(mul, range(1, r + 1), 1)
	return num // den
total = nCr(B, 2)
for i in Genres:
	if i > 1:
		total -= nCr(i, 2)
print(total)


from collections import defaultdict
X = list(map(int, input().split()))
MyDict = defaultdict(int)
for i in list(map(int, input().split())):
	MyDict[i] += 1
(SUM, Keys) = (0, list(MyDict.keys()))
for i in range(X[1]):
	for j in range(i + 1, X[1]):
		SUM += MyDict[Keys[i]] * MyDict[Keys[j]]
print(SUM)


def main():
	(n, m) = map(int, input().split())
	books = list(map(int, input().split()))
	genre = [0] * m
	for x in books:
		genre[x - 1] += 1
	options = 0
	for i in range(m - 1):
		for j in range(i + 1, m):
			options += genre[i] * genre[j]
	print(options)
main()


(n, m) = map(int, input().split())
a = list(map(int, input().split()))
from collections import Counter
c = Counter(a)
s = n * n
for i in c:
	s -= c[i] ** 2
print(s // 2)


(n, m) = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
p = a[0]
k = 0
ans = 0
for i in range(n):
	if p == a[i]:
		k += 1
	elif n - k > 0:
		ans += (n - k) * k
		n -= k
		k = 1
	p = a[i]
print(ans)


(n, m) = [int(_) for _ in input().split()]
ary = [int(_) for _ in input().split()]
ary2 = [0] * m
for i in ary:
	ary2[i - 1] += 1
c = n * (n - 1) // 2
for i in range(m):
	if ary2[i] > 1:
		c -= ary2[i] * (ary2[i] - 1) // 2
print(c)


(n, m) = map(int, input().split())
a = list(map(int, input().split()))
genres = [0] * m
cnt = 0
for x in a:
	genres[x - 1] += 1
for x in genres:
	cnt = cnt + x * (n - x)
print(cnt // 2)


split = lambda : list(map(int, input().split()))
(a, b) = split()
books = split()
types = []
for x in range(1, b + 1):
	types.append(books.count(x))
n = 0
for x in range(b - 1):
	for y in range(x + 1, b):
		n += types[x] * types[y]
print(n)


(n, m) = map(int, input().split())
b = list(map(int, input().split()))
gg = [0] * 11
for genre in b:
	gg[genre] += 1
ss = sum(gg)
ans = 0
for g in gg:
	ans += (ss - g) * g
print(int(ans / 2))


from collections import Counter
(n, m) = map(int, input().split())
arr = input().split()
c = Counter(arr)
s = n * (n - 1) // 2
for i in c:
	s -= c[i] * (c[i] - 1) // 2
print(s)


(num_books, num_genres) = [int(s) for s in input().split()]
counts = [0] * num_genres
for s in input().split():
	genre = int(s)
	counts[genre - 1] += 1
ans = 0
for genre1 in range(num_genres):
	for genre2 in range(genre1 + 1, num_genres):
		ans += counts[genre1] * counts[genre2]
print(ans)


def main():
	(n, m) = tuple(map(int, input().split()))
	genre_counts = [0] * m
	for g in map(int, input().split()):
		genre_counts[g - 1] += 1
	options = 0
	for c in genre_counts:
		options += c * (n - c)
	print(options // 2)
main()


import os
import sys
from io import BytesIO, IOBase
from collections import Counter

def main():
	(n, m) = map(int, input().split(' '))
	a = list(map(int, input().split(' ')))
	temp = Counter(a)
	l = len(temp)
	ans = 0
	for y in temp.values():
		ans += (n - y) * y
	print(ans // 2)
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()


def main():
	nm = input().split(' ')
	book = input().split(' ')
	n = int(nm[0])
	m = int(nm[1])
	result = 0
	array = [0 for i in range(m)]
	for i in book:
		array[int(i) - 1] += 1
	for i in range(m):
		s = 0
		for j in range(i + 1, m):
			s += array[j]
		result += array[i] * s
	print(result)
main()


from math import *
(n, m) = map(int, input().split())
a = list(map(int, input().split()))
all_m = 0
all_n = int(n * (n - 1) / 2)
for j in range(1, m + 1):
	all_m = a.count(j)
	if all_m > 1:
		all_n -= int(a.count(j) * (a.count(j) - 1) / 2)
print(all_n)


def total_sum(n):
	ans = 0
	for i in range(1, n):
		ans += i
	return ans
(n, m) = map(int, input().split())
x = list(map(int, input().split()))
total_genres = 11 * [0]
for i in range(n):
	total_genres[x[i]] += 1
ans = total_sum(n)
for j in range(m + 1):
	if total_genres[j] > 1:
		ans -= total_sum(total_genres[j])
print(ans)


from collections import Counter
(n, m) = map(int, input().split())
arr = list(map(int, input().split()))
count = 0
result = 0
sort_arr = sorted(arr)
count_arr = list(Counter(sort_arr).values())
for i in range(len(count_arr)):
	result += count_arr[i] * count
	count = count_arr[i] + count
print(result)


(nBooks, nGenres) = [int(x) for x in input().split()]
genres = [0] * (nGenres + 1)
for x in input().split():
	genres[int(x)] += 1
sol = nBooks * (nBooks - 1) // 2
for genre in genres:
	if genre > 1:
		sol -= genre * (genre - 1) // 2
print(sol)


(n, m) = map(int, input().split())
arr = list(map(int, input().split()))
dict = {}
for i in range(n):
	genre = arr[i]
	if genre in dict:
		dict[genre] += 1
	else:
		dict[genre] = 1
count = 0
for i in range(1, m):
	for j in range(i + 1, m + 1):
		count += dict[i] * dict[j]
print(count)


(n, m) = map(int, input().strip().split())
g = [0] * m
for a in map(int, input().strip().split()):
	g[a - 1] += 1
total = 0
for i in range(m):
	for j in range(i + 1, m):
		total += g[i] * g[j]
print(total)


(n, m) = map(int, input().split())
books = list(map(int, input().split()))
category = [0] * (m + 1)
for book in books:
	category[book] += 1
result = 0
for book in category:
	result += (n - book) * book
print(result // 2)


Maxnum = 10
(n, m) = map(int, input().split())
genres = [0] * (Maxnum + 1)
ans = 0
for i in map(int, input().split()):
	genres[i] += 1
for i in range(1, Maxnum):
	for j in range(i + 1, Maxnum + 1):
		ans += genres[i] * genres[j]
print(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())
(n, m) = mints()
c = [0] * 11
for i in mints():
	c[i] += 1
r = 0
for i in range(11):
	for j in range(i + 1, 11):
		r += c[i] * c[j]
print(r)


(n, m) = input().split()
a = input().split()
m = int(m)
n = int(n)
waka = n * (n - 1) / 2
z = 0
for i in range(1, m + 1):
	p = 0
	for j in range(len(a)):
		if i == int(a[j]):
			p += 1
	z += p * (p - 1) / 2
print(int(waka - z))


def intline():
	return [int(i) for i in input().split()]
(n, m) = intline()
l = [0] * m
for i in intline():
	l[i - 1] += 1
total = sum((l[i] * sum(l[i + 1:]) for i in range(m)))
print(total)


(n, m) = map(int, input().split())
a = list(map(int, input().split()))
cnt = [0] * 11
for ai in a:
	cnt[ai] += 1
res = 0
for b1 in range(1, m + 1):
	for b2 in range(b1 + 1, m + 1):
		res += cnt[b1] * cnt[b2]
print(res)


def ncr(t):
	return int(t * (t - 1) / 2)
user_input = input()
(a, b) = user_input.split()
a = int(a)
b = int(b)
x = [0 for l in range(b + 1)]
limt = input()
limt = limt.split()
for y in limt:
	x[int(y)] += 1
ans = ncr(a)
for i in range(1, b + 1):
	ans -= ncr(x[i])
print(ans)


ans = 0
(n, m) = [int(x) for x in input().split()]
b = [int(x) for x in input().split()]
tmp = [0] * 11
for k in b:
	tmp[k] += 1
ans = 0
for i in range(1, m + 1):
	for j in range(i + 1, m + 1):
		ans += tmp[i] * tmp[j]
	for j in range(i - 1, -1, -1):
		ans += tmp[i] * tmp[j]
print(ans // 2)


x = []
x = input().split()
n = int(x[0])
m = int(x[1])
a = []
a = input().split()
s = {}
for i in range(n):
	try:
		s[a[i]] += 1
	except KeyError:
		s[a[i]] = 1
ans = n * (n - 1) / 2
for i in s.values():
	if i != 1:
		ans -= i * (i - 1) / 2
print(int(ans))


from math import floor
from functools import reduce

def ncr(n, r):
	return floor(reduce(lambda x, y: x * y, [(n - i) / (i + 1) for i in range(r)]))

def main():
	[nBooks, nGenres] = list(map(int, input().split(' ')))
	books = list(map(int, input().split(' ')))
	genreCounts = {}
	for genre in books:
		if genre not in genreCounts:
			genreCounts[genre] = 1
		else:
			genreCounts[genre] += 1
	numInvalidPairs = 0
	for (_, v) in genreCounts.items():
		numInvalidPairs += ncr(v, 2)
	print('{}'.format(floor(ncr(len(books), 2) - numInvalidPairs)))
main()


(n, m) = map(int, input().split())
ls = list(map(int, input().split()))
cnt = [0 for i in range(m + 1)]
for i in range(n):
	cnt[ls[i]] += 1
sum = 0
for i in range(1, m + 1, 1):
	for j in range(i + 1, m + 1, 1):
		sum = sum + cnt[i] * cnt[j]
print(sum)


(n, m) = map(int, input().split())
A = list(map(int, input().split()))

def Sort(A):
	B = [0 for i in range(m + 1)]
	for i in A:
		B[i] += 1
	return B
B = Sort(A)
ans = n * (n - 1) // 2
for i in B:
	ans -= i * (i - 1) // 2
print(ans)


(n, m) = map(int, input().split())
genres = list(map(int, input().split()))
genre_frequencies = [0 for i in range(m + 1)]
for genre in genres:
	genre_frequencies[genre] += 1
all_pairs = n * (n - 1) // 2
bad_pairs = 0
for freq in genre_frequencies:
	bad_pairs += freq * (freq - 1) // 2
print(all_pairs - bad_pairs)


import sys
from collections import Counter
(n, m) = map(int, input().split())
cnt = Counter(map(int, input().split()))
ans = 0
for (k, v) in cnt.items():
	n -= v
	ans += v * n
print(ans)


(n, m) = [int(x) for x in input().split()]
import math
from collections import Counter
from itertools import combinations
cnt = Counter(input().split())
res = 0
for c in combinations(cnt.keys(), 2):
	res += cnt[c[0]] * cnt[c[1]]
print(res)


R = lambda : map(int, input().split())
(n, m) = R()
v = [0] * m
r = [0] * m
for i in R():
	v[i - 1] += 1
for i in reversed(range(m - 1)):
	r[i] = r[i + 1] + v[i + 1]
s = 0
for i in range(m):
	s += v[i] * r[i]
print(s)


def main():
	(n, m) = map(int, input().split())
	books = list(map(int, input().split()))
	dist_books = {}
	for i in books:
		if i not in dist_books.keys():
			dist_books[i] = 0
		dist_books[i] += 1
	ways = 0
	for i in dist_books.keys():
		ways += dist_books[i] * (n - dist_books[i])
	print(ways // 2)
main()


(n, m) = [int(i) for i in input().split()]
booklist = [int(i) for i in input().split()]
bookcount = []
step1 = 0
step2 = 1
final = 0
for i in range(1, m + 1):
	count = 0
	for j in booklist:
		if j == i:
			count += 1
	bookcount.append(count)
while step1 < m - 1:
	if step2 < m:
		final += bookcount[step1] * bookcount[step2]
		step2 += 1
	else:
		step1 += 1
		step2 = step1 + 1
print(final)


(n, m) = map(int, input().split())
books_per_genre = [0] * m
books = list(map(int, input().split()))
for book in books:
	books_per_genre[book - 1] += 1
result = 0
used = 0
for genre in books_per_genre:
	result += genre * (n - genre - used)
	used += genre
print(result)


from collections import Counter
(n, m) = map(int, input().split())
a = Counter(map(int, input().split()))
b = list(a.values())
r = 0
for i in range(len(b)):
	for j in range(i + 1, len(b)):
		r += b[i] * b[j]
print(r)


(n, m) = map(int, input().split())
A = list(map(int, input().split()))
from collections import defaultdict
d = defaultdict(lambda : 0)
for a in A:
	d[a] += 1
import itertools
ans = 0
for c in itertools.combinations(range(1, m + 1), 2):
	(i, j) = c
	ans += d[i] * d[j]
print(ans)


import math
(n, m) = map(int, input().split())
a = list(map(int, input().split()))
b = [0 for _ in range(m)]
for i in range(n):
	b[a[i] - 1] += 1
total = n * (n - 1) / 2
for i in range(m):
	if b[i] > 1:
		total -= b[i] * (b[i] - 1) / 2
print(int(total))


(n, m) = map(int, input().split())
l = list(map(int, input().split()))
count = [0] * m
for i in l:
	count[i - 1] += 1
sum = 0
for i in range(0, m):
	for j in range(i + 1, m):
		sum += count[i] * count[j]
print(sum)


import math

def e(x, y):
	if x > y:
		return 0
	return math.factorial(y) / (math.factorial(y - x) * math.factorial(x))
a = input()
b = input()
a = a.split(' ')
n = int(a[0])
m = int(a[1])
b = b.split(' ')
t = 0
k = [0 for p in range(m)]
z = 0
for f in b:
	f = int(f)
	k[f - 1] += 1
	z += 1
	t += z - k[f - 1]
print(int(t))


(n, m) = list(map(int, input().split()))
a = list(map(int, input().split()))
cnt = [0] * m
for el in a:
	cnt[el - 1] += 1
res = 0
for i in range(m):
	for j in range(m):
		if i >= j:
			continue
		res += cnt[i] * cnt[j]
print(res)


(n, m) = map(int, input().split())
arr = list(map(int, input().split()))
li = [0] * (n + 1)
for i in arr:
	li[i] += 1
sum = n * (n - 1) // 2
for i in range(0, n + 1):
	if li[i]:
		sum -= li[i] * (li[i] - 1) // 2
print(sum)