Since Sonya is interested in robotics too, she decided to construct robots that will read and recognize numbers.

Sonya has drawn $n$ numbers in a row, $a_i$ is located in the $i$-th position. She also has put a robot at each end of the row (to the left of the first number and to the right of the last number). Sonya will give a number to each robot (they can be either same or different) and run them. When a robot is running, it is moving toward to another robot, reading numbers in the row. When a robot is reading a number that is equal to the number that was given to that robot, it will turn off and stay in the same position.

Sonya does not want robots to break, so she will give such numbers that robots will stop before they meet. That is, the girl wants them to stop at different positions so that the first robot is to the left of the second one.

For example, if the numbers $[1, 5, 4, 1, 3]$ are written, and Sonya gives the number $1$ to the first robot and the number $4$ to the second one, the first robot will stop in the $1$-st position while the second one in the $3$-rd position. In that case, robots will not meet each other. As a result, robots will not be broken. But if Sonya gives the number $4$ to the first robot and the number $5$ to the second one, they will meet since the first robot will stop in the $3$-rd position while the second one is in the $2$-nd position.

Sonya understands that it does not make sense to give a number that is not written in the row because a robot will not find this number and will meet the other robot.

Sonya is now interested in finding the number of different pairs that she can give to robots so that they will not meet. In other words, she wants to know the number of pairs ($p$, $q$), where she will give $p$ to the first robot and $q$ to the second one. Pairs ($p_i$, $q_i$) and ($p_j$, $q_j$) are different if $p_i\neq p_j$ or $q_i\neq q_j$.

Unfortunately, Sonya is busy fixing robots that broke after a failed launch. That is why she is asking you to find the number of pairs that she can give to robots so that they will not meet.


-----Input-----

The first line contains a single integer $n$ ($1\leq n\leq 10^5$) — the number of numbers in a row.

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1\leq a_i\leq 10^5$) — the numbers in a row.


-----Output-----

Print one number — the number of possible pairs that Sonya can give to robots so that they will not meet.


-----Examples-----
Input
5
1 5 4 1 3

Output
9

Input
7
1 2 1 1 1 3 2

Output
7



-----Note-----

In the first example, Sonya can give pairs ($1$, $1$), ($1$, $3$), ($1$, $4$), ($1$, $5$), ($4$, $1$), ($4$, $3$), ($5$, $1$), ($5$, $3$), and ($5$, $4$).

In the second example, Sonya can give pairs ($1$, $1$), ($1$, $2$), ($1$, $3$), ($2$, $1$), ($2$, $2$), ($2$, $3$), and ($3$, $2$).

Source: codeforces | Difficulty: MEDIUM
Tags: Implementation

Constructive algorithms


Solutions:
n = int(input())
a = [int(i) for i in input().split()]
dic = {}
dic1 = {}
arr = [0] * n
count1 = 0
for i in range(n - 1, 0, -1):
	if a[i] not in dic.keys():
		dic[a[i]] = 1
		count1 += 1
	arr[i - 1] = count1
count = 0
for i in range(n - 1):
	if a[i] not in dic1.keys():
		dic1[a[i]] = 1
		count += arr[i]
print(count)


from collections import Counter
n = int(input())
a = list(map(int, input().split()))
d = Counter(a)
count = 0
blackset = set()
rs = set(a)
for i in range(n - 1):
	d[a[i]] -= 1
	if d[a[i]] == 0:
		rs.remove(a[i])
	if a[i] not in blackset:
		blackset.add(a[i])
		count += len(rs)
print(count)


n = int(input())
a = list(map(int, input().split()))
cnt = [0] * (10 ** 5 + 4)
l = 0
dis = []
for i in range(n - 1):
	if cnt[a[i]] == 0:
		cnt[a[i]] += 1
		l += 1
	dis.append(l)
done = [0] * (10 ** 5 + 4)
ans = 0
for i in range(n - 1, 0, -1):
	if done[a[i]] == 0:
		ans += dis[i - 1]
		done[a[i]] += 1
print(ans)


from bisect import *
N = 100001
input()
l = [N] * N
r = [0] * N
for (i, x) in enumerate(map(int, input().split())):
	l[x] = min(l[x], i)
	r[x] = i
l.sort()
print(sum((bisect_left(l, x) for x in r)))


n = int(input())
l = list(map(int, input().split()))
d = {}
d1 = {-1}
s = set(l)
k = 0
for x in l:
	d[x] = d.get(x, 0) + 1
for x in l:
	if x not in d1:
		if d[x] == 1:
			s.remove(x)
		k += len(s)
		d1.add(x)
		d[x] -= 1
	else:
		d[x] -= 1
		if d[x] == 0:
			s.remove(x)
print(k)


import sys
input = sys.stdin.readline
from collections import Counter
n = int(input())
a = list(map(int, input().split()))
right_counts = Counter(a)
can_be_left = [1] * (10 ** 5 + 1)
res = 0
for num in a:
	if can_be_left[num]:
		right_counts[num] -= 1
		if not right_counts[num]:
			del right_counts[num]
		res += len(right_counts)
		can_be_left[num] = 0
	else:
		right_counts[num] -= 1
		if not right_counts[num]:
			del right_counts[num]
print(res)


from collections import Counter
n = int(input())
arr = list(map(int, input().split()))
ctr = Counter(arr)
visited = set()
ans = 0
for i in range(n - 1):
	if ctr[arr[i]] == 1:
		del ctr[arr[i]]
	else:
		ctr[arr[i]] -= 1
	if arr[i] not in visited:
		ans += len(ctr)
		visited.add(arr[i])
print(ans)


n = int(input())
if n == 1:
	print(0)
else:
	a = list(map(int, input().split()))
	l = [0 for i in range(n - 1)]
	s = set()
	s.add(a[-1])
	l[-1] = 1
	for i in range(n - 2, 0, -1):
		if a[i] not in s:
			s.add(a[i])
			l[i - 1] = l[i] + 1
		else:
			l[i - 1] = l[i]
	s2 = set()
	p = 0
	for i in range(n - 1):
		if a[i] not in s2:
			s2.add(a[i])
			p += l[i]
	print(p)


import math

def problem(in1, in2):
	n = int(in1)
	numbers = list(map(int, in2.split()))
	robo1 = []
	set1 = set()
	for num in numbers:
		robo1.append(num not in set1)
		set1.add(num)
	set2 = set()
	robo2 = []
	count = 0
	for num in numbers[::-1]:
		if num not in set2:
			count += 1
		set2.add(num)
		robo2.append(count)
	robo2.reverse()
	robo2.append(0)
	result = 0
	for (i, unique) in enumerate(robo1):
		if unique:
			result += robo2[i + 1]
	return result
in1 = input()
in2 = input()
result = problem(in1, in2)
print(result)


total = int(input())
inputs = [int(x) for x in input().split(' ')]
alldig = {}
s = set()
for x in inputs:
	if x in alldig:
		alldig[x] += 1
	else:
		alldig[x] = 1
out = 0
for x in inputs:
	if alldig[x] == 1:
		alldig.pop(x)
	else:
		alldig[x] -= 1
	if x not in s:
		s.add(x)
		out += len(alldig)
print(out)


n = int(input().strip())
data = list(map(int, input().split()))
s = set()
prev = dict()
ans = 0
for val in data:
	if val in prev:
		ans -= prev[val]
	prev[val] = len(s)
	ans += prev[val]
	s.add(val)
print(ans)


n = int(input())
a = list(map(int, input().split()))
N = 100005
lt = [0] * N
rt = [0] * N
used = [False] * N
for i in range(n):
	if not used[a[i]]:
		used[a[i]] = True
		lt[i] += 1
used = [False] * N
sum = 0
ans = 0
for i in range(n - 1, -1, -1):
	if not used[a[i]]:
		used[a[i]] = True
		rt[i] += 1
		sum += 1
for i in range(n):
	sum -= rt[i]
	ans += lt[i] * sum
print(ans)


from collections import defaultdict
n = int(input())
A = list(map(int, input().split()))
d = defaultdict(int)
for x in A:
	d[x] += 1
count = 0
skip = set()
for i in range(len(A) - 1):
	d[A[i]] -= 1
	if d[A[i]] == 0:
		del d[A[i]]
	if A[i] in skip:
		continue
	count += len(d)
	skip.add(A[i])
print(count)


n = int(input())
x = [0 for i in range(100009)]
y = [0 for i in range(100009)]
a = [int(i) for i in input().split()]
for i in a:
	x[i] += 1
count = 0
p = 0
for i in range(len(a)):
	y[a[i]] += 1
	if x[a[i]] != 1 and y[a[i]] != x[a[i]]:
		count -= p
	if y[a[i]] == 1:
		count += n - 1 - i
		p += 1
print(count)


input()
s = set()
c = [0] * 100006
for x in map(int, input().split()):
	c[x] = len(s)
	s.add(x)
print(sum(c))


n = int(input())
a = list(map(int, input().split()))
d = {}
for i in range(n):
	if d.get(a[i]) == None:
		d[a[i]] = 1
	else:
		d[a[i]] += 1
count = 0
used = set()
for i in range(n):
	d[a[i]] -= 1
	if d[a[i]] == 0:
		del d[a[i]]
	if a[i] not in used:
		count += len(d)
	used.add(a[i])
print(count)


def scanf(t=int):
	return list(map(t, input().split()))
(n,) = scanf()
m = scanf()
(used, dp) = (set(), [0] * n)
for i in range(n - 2, -1, -1):
	dp[i] = dp[i + 1] + (m[i + 1] not in used)
	used.add(m[i + 1])
(ans, used) = (0, set())
for i in range(n - 1):
	if m[i] not in used:
		ans += dp[i]
	used.add(m[i])
print(ans)


n = int(input())
a = list(map(int, input().split()))
b = [0] * (n + 1)
s = set()
ans = 0
hm = [0] * 100010
for i in range(n - 1, -1, -1):
	s.add(a[i])
	b[i] = len(s)
for i in range(n - 1):
	if not hm[a[i]]:
		hm[a[i]] += 1
		ans += b[i + 1]
print(ans)


def solve():
	n = int(input())
	nums = list(map(int, input().split()))
	seen = set()
	num_distinct = [0 for _ in range(n + 1)]
	for i in reversed(range(n)):
		if nums[i] not in seen:
			seen.add(nums[i])
			num_distinct[i] = num_distinct[i + 1] + 1
		else:
			num_distinct[i] = num_distinct[i + 1]
	seen = set()
	ans = 0
	for i in range(len(nums)):
		if nums[i] in seen:
			continue
		ans += num_distinct[i + 1]
		seen.add(nums[i])
	print(ans)
solve()


from collections import defaultdict as dc
n = int(input())
a = list(map(int, input().split()))
cnt = dc(int)
cnt2 = dc(int)
for i in range(n):
	cnt2[a[i]] += 1
l = len(set(a))
ans = 0
for i in range(n - 1):
	cnt2[a[i]] -= 1
	if cnt2[a[i]] == 0:
		l -= 1
	if cnt[a[i]]:
		continue
	ans += l
	cnt[a[i]] += 1
print(ans)


from collections import defaultdict
n = int(input())
a = [int(i) for i in input().split()]
done = set()
d = defaultdict(int)
for i in a:
	d[i] += 1
c = len(list(d.keys()))
total = 0
for i in a:
	d[i] -= 1
	if d[i] == 0:
		c -= 1
	if i not in done:
		total += c
		done.add(i)
print(total)


n = int(input())
d = {}
for i in input().split():
	d[i] = len(d)
print(sum(d.values()))


n = int(input())
a = input().split()
cou = [0 for i in range(100005)]
vis = [False for i in range(100005)]
st = set()
for i in range(n):
	a[i] = int(a[i])
	cou[a[i]] += 1
	st.add(a[i])
ans = 0
for i in range(n):
	cou[a[i]] -= 1
	if cou[a[i]] == 0:
		st.remove(a[i])
	if vis[a[i]] == False:
		vis[a[i]] = True
		ans += len(st)
print(ans)


n = int(input())
nums = list(map(int, input().split()))
left = {}
from collections import Counter
left = Counter(nums)
count = 0
done = set()
for i in nums:
	left[i] -= 1
	if left[i] == 0:
		del left[i]
	if i not in done:
		count += len(left.keys())
		done.add(i)
print(count)


n = int(input())
var = 0
v = [False] * (10 ** 5 + 1)
ls = list(map(int, input().split()))
arr = [0] * n
cnt = 0
for i in range(n - 1, -1, -1):
	if v[ls[i]] == False:
		cnt += 1
		v[ls[i]] = True
	arr[i] = cnt
v = [False] * (10 ** 5 + 1)
for i in range(n - 1):
	if v[ls[i]] == False:
		var += arr[i + 1]
		v[ls[i]] = True
print(var)


import collections
from functools import cmp_to_key
import math
import sys

def getIntList():
	return list(map(int, input().split()))
import bisect
try:
	import numpy
	dprint = print
	dprint('debug mode')
except ModuleNotFoundError:

	def dprint(*args, **kwargs):
		pass

def makePair(z):
	return [(z[i], z[i + 1]) for i in range(0, len(z), 2)]

def memo(func):
	cache = {}

	def wrap(*args):
		if args not in cache:
			cache[args] = func(*args)
		return cache[args]
	return wrap

@memo
def comb(n, k):
	if k == 0:
		return 1
	if n == k:
		return 1
	return comb(n - 1, k - 1) + comb(n - 1, k)
(n,) = getIntList()
za = getIntList()
ff = [0 for _ in range(110000)]
hap = []
for i in range(n):
	x = za[i]
	if ff[x] != 0:
		continue
	hap.append(i)
	ff[x] = 1
dprint(hap)
ff = [0 for _ in range(110000)]
import bisect
res = 0
last = len(hap) - 1
for i in range(n - 1, -1, -1):
	x = za[i]
	if ff[x] != 0:
		continue
	ff[x] = 1
	while last >= 0 and hap[last] >= i:
		last -= 1
	res += last + 1
print(res)


n = int(input())
arr = list(map(int, input().split()))
arr1 = [0] * (n + 1)
arr2 = [0] * (n + 1)
if n == 1:
	print(0)
else:
	ans = 0
	var = 1
	arr2[arr[-1]] = 1
	for i in range(n - 2, -1, -1):
		if arr2[arr[i]] == 0:
			ans += var
			arr1[arr[i]] = var
			var += 1
			arr2[arr[i]] += 1
		elif arr2[arr[i]] == 1:
			ans -= arr1[arr[i]]
			ans += var
			arr2[arr[i]] += 1
			arr1[arr[i]] = var
		else:
			ans -= arr1[arr[i]]
			ans += var
			arr1[arr[i]] = var
			arr2[arr[i]] += 1
	print(ans)


import sys
n = int(input())
s = list(map(int, input().split()))
if n == 1:
	print(0)
	sys.exit()
st = []
st1 = []
d = dict()
sett = set()
s1 = s[::-1]
y = 0
for i in range(n):
	if s1[i] not in sett:
		y += 1
		sett.add(s1[i])
	st1.append(y)
st1 = st1[0:len(st1) - 1][::-1]
for i in range(0, n):
	try:
		d[s[i]]
	except:
		d.update({s[i]: i})
ans = 0
for i in range(0, n - 1):
	if d[s[i]] == i:
		ans += st1[i]
print(ans)


n = int(input())
a = [int(x) for x in input().split()]
MAX_NUM = 100010
met_forw = [False] * MAX_NUM
met_backw = [False] * MAX_NUM
unique_n_backw = [0] * n
for i in range(n - 1, -1, -1):
	if i < n - 1:
		unique_n_backw[i] = unique_n_backw[i + 1]
	if not met_backw[a[i]]:
		met_backw[a[i]] = True
		unique_n_backw[i] += 1
answer = 0
for i in range(n - 1):
	if not met_forw[a[i]]:
		met_forw[a[i]] = True
		answer += unique_n_backw[i + 1]
print(answer)


n = int(input())
row = [int(i) for i in input().strip().split()]
q_set = set()
q_possibilities = []
for i in range(-1, -n, -1):
	q_set.add(row[i])
	q_possibilities.append(len(q_set))
q_possibilities.append(0)
q_possibilities.reverse()
p_set = set()
my_sum = 0
for i in range(n - 1):
	if row[i] not in p_set:
		p_set.add(row[i])
		my_sum = my_sum + q_possibilities[i + 1]
print(my_sum)


from collections import Counter
n = int(input())
l = list(map(int, input().split()))
c = Counter(l)
ans = 0
s = set()
for i in range(n):
	if set(l[i:i + 1]).issubset(s):
		c[l[i]] -= 1
		if c[l[i]] == 0:
			del c[l[i]]
		continue
	s.add(l[i])
	if c[l[i]] > 1:
		c[l[i]] -= 1
		ans += len(c.keys())
	elif c[l[i]] == 1:
		del c[l[i]]
		ans += len(c.keys())
print(ans)


input()
numbers = list(input().split())
repeated_numbers = {}
counter = 0
for number in numbers:
	counter += len(repeated_numbers)
	if number in repeated_numbers:
		counter -= repeated_numbers[number]
	repeated_numbers[number] = len(repeated_numbers)
print(counter)


from math import *
import sys

def main():
	n = int(input().strip())
	a = [int(x) for x in input().split(' ')]
	first = {}
	for i in range(len(a)):
		if a[i] not in first:
			first[a[i]] = i
	sz = [0 for i in range(n + 3)]
	m = {}
	for i in range(n - 1, -1, -1):
		cur_n = a[i]
		m[cur_n] = m[cur_n] + 1 if cur_n in m else 1
		sz[i] = len(m)
	cnt = 0
	for i in range(n):
		if first[a[i]] == i:
			cnt += sz[i + 1]
	print(cnt)
main()


from collections import defaultdict
n = int(input())
a = list(map(int, input().split()))
d = defaultdict(int)
dis = defaultdict(int)
s = set()
s.add(a[-1])
c = 1
dis[n - 1] = 1
for i in range(n - 2, -1, -1):
	d[a[i]] = i
	if a[i] not in s:
		c += 1
		s.add(a[i])
	dis[i] = c
ans = 0
for i in d:
	ans += dis[d[i] + 1]
print(ans)


n = int(input())
arr = list(map(int, input().split()))
pst = [0] * 100001
left = [0] * n
right = [0] * n
for i in range(n - 1, -1, -1):
	if i == n - 1:
		pst[arr[i]] = 1
		right[i] = 1
	elif pst[arr[i]] == 0:
		right[i] = right[i + 1] + 1
		pst[arr[i]] = 1
	else:
		right[i] = right[i + 1]
pst = [0] * 100001
ans = 0
for i in range(n - 1):
	if pst[arr[i]] == 0:
		pst[arr[i]] = 1
		ans += right[i + 1]
print(ans)


n = int(input())
A = list(map(int, input().split()))
nb = 0
all = [0 for _ in range(10 ** 5)]
distinct = len(set(A))
seen = [False for _ in range(10 ** 5)]
for x in A:
	all[x - 1] += 1
for i in range(n - 1):
	all[A[i] - 1] -= 1
	if all[A[i] - 1] == 0:
		distinct -= 1
	if not seen[A[i] - 1]:
		seen[A[i] - 1] = True
		nb += distinct
print(nb)


import sys
input = sys.stdin.readline
from collections import defaultdict
from bisect import *
n = int(input())
a = list(map(int, input().split()))
ld = defaultdict(int)
for i in range(n):
	if a[i] not in ld:
		ld[a[i]] = i
rd = defaultdict(int)
for i in range(n - 1, -1, -1):
	if a[i] not in rd:
		rd[a[i]] = i
l = list(rd.values())
l.reverse()
ans = 0
for ai in ld.keys():
	ans += len(rd) - bisect_right(l, ld[ai])
print(ans)


import sys
input = lambda : sys.stdin.readline()
MOD = 1000000007
ii = lambda : int(input())
si = lambda : input()
dgl = lambda : list(map(int, input()))
f = lambda : list(map(int, input().split()))
il = lambda : list(map(int, input().split()))
ls = lambda : list(input())
(df, db) = (set(), {})
n = ii()
l = il()
for i in l:
	db[i] = db.get(i, 0) + 1
c = 0
uniq = 0
for i in range(n):
	db[l[i]] -= 1
	if db[l[i]] == 0:
		db.pop(l[i])
	if not l[i] in df:
		uniq += 1
		df.add(l[i])
		c += len(db)
print(c)


n = int(input())
l = list(map(int, input().split()))
d1 = dict()
d2 = dict()
for i in range(n):
	if l[i] not in d1:
		d1[l[i]] = i
for i in reversed(range(n)):
	if l[i] not in d2:
		d2[l[i]] = i
start = sorted(list(d1.values()))
end = sorted(list(d2.values()))
tec = 0
k = 0
c = len(end)
cold = c
for elem in start:
	while end[tec] <= elem:
		tec += 1
		c -= 1
		if tec == cold:
			break
	k += c
print(k)


from collections import Counter
n = int(input())
a = [int(x) for x in input().split()]
d = Counter(a)
sa = set(a)
la = set()
sum = 0
for i in range(n):
	d[a[i]] -= 1
	if d[a[i]] == 0:
		sa.remove(a[i])
	if a[i] in la:
		continue
	else:
		la.add(a[i])
	sum += len(sa)
print(sum)


n = int(input())
arr = [int(x) for x in input().split()]
num___fl = {}
num___fr = {}
for (i, num) in enumerate(arr):
	if num not in num___fl:
		num___fl[num] = i
	if num not in num___fr:
		num___fr[num] = i
	elif num___fr[num] < i:
		num___fr[num] = i
fls_asc = list(sorted(num___fl.values()))
frs_asc = list(sorted(num___fr.values()))
ir = 0
ans = 0
for (il, fl) in enumerate(fls_asc):
	while True:
		if ir >= len(frs_asc):
			break
		if frs_asc[ir] > fl:
			break
		ir += 1
	ans += len(frs_asc) - ir
print(ans)


from sys import stdin, stdout
n = int(stdin.readline())
a = list(map(int, stdin.readline().split()))
cnt = [0] * int(200000.0)
cur = set()
for ai in a:
	cnt[ai] = len(cur)
	cur.add(ai)
stdout.write(str(sum(cnt)))


input()
d = {}
for x in map(int, input().split()):
	d[x] = len(d)
print(sum(d.values()))


n = int(input())
a = [int(x) for x in input().strip().split()]
f = dict()
b = dict()
for i in range(len(a)):
	if a[i] not in f:
		f[a[i]] = i
	if a[n - 1 - i] not in b:
		b[a[n - 1 - i]] = n - 1 - i
f = sorted(([v, k] for (k, v) in f.items()))
b = sorted(([v, k] for (k, v) in b.items()))
ans = 0
bi = 0
for (i, v) in f:
	while bi < len(b) and i >= b[bi][0]:
		bi += 1
	ans += len(b) - bi
print(ans)


n = int(input())
s = input().split()
a = [0] * n
b = [0] * 100001
c = [0] * 100001
k = 0
for i in range(n):
	a[i] = int(s[i])
	if b[a[i]] == 0:
		k += 1
	b[a[i]] += 1
m = 0
for i in range(n - 1):
	b[a[i]] -= 1
	if b[a[i]] == 0:
		k -= 1
	if c[a[i]] == 0:
		c[a[i]] = 1
		m += k
print(m)


n = int(input())
a = list(map(int, input().split()))
count = 0
d = {}
k = []
for i in range(len(a)):
	d[a[i]] = 0
start = a[0]
k.append(a[0])
for i in range(1, len(a)):
	if d[a[i]] != 0 or a[i] == start:
		d[a[i]] = len(k)
	else:
		d[a[i]] = len(k)
		k.append(a[i])
for i in range(len(k)):
	count += len(k) - (i + 1)
	if d[k[i]] != i:
		count += d[k[i]] - i
print(count)


import collections
line = input().split()
n = int(line[0])
a = [int(ai) for ai in input().split()]
if n <= 1:
	print(0)
	exit()
left = {a[0]}
right = collections.defaultdict(lambda : 0)
for ai in a[1:]:
	right[ai] = right[ai] + 1
res = 0
res += len(right)
for i in range(1, n):
	right[a[i]] -= 1
	if right[a[i]] == 0:
		del right[a[i]]
	if a[i] in left:
		continue
	else:
		left.add(a[i])
		res += len(right)
print(res)


n = int(input())
a = list(map(int, input().split()))
l = [-1] * 100200
r = [-1] * 100200
b = [0] * 100200
for i in range(n):
	x = a[i]
	if l[x] == -1:
		l[x] = i
	r[x] = i
for i in range(100100):
	if l[i] != -1:
		b[l[i]] += 1
for i in range(1, 100100):
	b[i] += b[i - 1]
ans = 0
for i in range(1, 100100):
	if r[i] != -1:
		ans += b[r[i] - 1]
print(ans)


def I():
	return [int(i) for i in input().split()]
n = I()
l = I()
from collections import Counter as C
c = C(l)
c[l[0]] -= 1
s = len(c)
sum = s
if c[l[0]] == 0:
	s -= 1
	sum = s
se = set()
se.add(l[0])
for i in l[1:]:
	c[i] -= 1
	if c[i] == 0:
		s -= 1
	if i in se:
		continue
	se.add(i)
	sum += s
print(sum)


n = int(input())
arr = list(map(int, input().split()))
d = {}
for i in arr:
	d[i] = d.get(i, 0) + 1
ans = 0
s = set()
for i in arr:
	d[i] = d.get(i, 0) - 1
	if d[i] == 0:
		del d[i]
	if i not in s:
		ans += len(d)
	s.add(i)
print(ans)


n = int(input())
l = [int(x) for x in input().split()]
d = {}
for i in l:
	if i in d:
		d[i] += 1
	else:
		d[i] = 1
d1 = d
u = []
for i in l:
	if i in d:
		d[i] -= 1
		if d[i] == 0:
			d.pop(i, None)
	u.append(len(d))
d.clear()
count = 0
for i in range(len(l)):
	if l[i] in d:
		continue
	d[l[i]] = 1
	count += u[i]
print(count)


import math as ma
from sys import exit
from decimal import Decimal as dec

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

def num():
	return map(int, input().split())

def nu():
	return int(input())
n = nu()
a = li()
f = [-1] * 100001
z = [0] * n
c = 0
for i in range(len(a) - 1, 0, -1):
	if f[a[i]] == -1:
		c += 1
		z[i] = c
		f[a[i]] = 1
	else:
		z[i] = c
f = [-1] * 100001
xx = 0
for i in range(n - 1):
	if f[a[i]] == -1:
		xx += z[i + 1]
		f[a[i]] = 1
print(xx)


def ii():
	return int(input())

def mi():
	return map(int, input().split())

def li():
	return list(mi())
n = ii()
a = li()
ans = 0
cnt = [0] * (10 ** 5 + 10)
cur = set()
for ai in a:
	cnt[ai] = len(cur)
	cur.add(ai)
ans = sum(cnt)
print(ans)


n = int(input())
a = list(map(int, input().split()))
b = set()
c = []
s = 0
for i in a:
	if not i in b:
		s += 1
		b.add(i)
	c.append(s)
b = set()
ans = 0
for i in range(n - 1, 0, -1):
	if not a[i] in b:
		ans += c[i - 1]
		b.add(a[i])
print(ans)


n = int(input())
seq = [int(x) for x in input().split()]
sf = {}
ss = {}
for i in range(n):
	ss[seq[i]] = i + 1
for i in range(n):
	sf[seq[n - i - 1]] = n - i
list1 = sorted(sf.values(), reverse=True)
list2 = sorted(ss.values(), reverse=True)
i1 = 0
i2 = 0
tot = 0
leq = 0
while i1 < len(list1) and list1[i1] >= list2[i2]:
	i1 += 1
while i1 < len(list1):
	while i2 < len(list1) and list1[i1] < list2[i2]:
		i2 += 1
	if list1[i1] < list2[i2 - 1]:
		tot += i2
	i1 += 1
print(tot)


n = int(input())
lst = list(map(int, input().split()))
came = [False] * (10 ** 5 + 1)
right = [-1] * (10 ** 5 + 1)
unique = []
duplet = set()
ans = 0
for (i, item) in enumerate(lst):
	if came[item]:
		duplet.add(item)
		ans += unique[-1] - unique[right[item]]
		unique.append(unique[-1])
	else:
		try:
			ans += unique[-1]
			unique.append(unique[-1] + 1)
		except:
			ans = 0
			unique = [1]
		came[item] = True
	right[item] = i
print(ans + len(duplet))


n = int(input())
arr = list(map(int, input().split()))
dic = {}
dic2 = {}
ansar = []
for i in range(n):
	dic[arr[i]] = 0
	dic2[arr[i]] = 0
	ansar.append(0)
count = 0
for i in range(n - 1, 0, -1):
	if dic[arr[i]] == 0:
		count += 1
		dic[arr[i]] = 1
	ansar[i - 1] = count
answer = 0
for i in range(n - 1):
	if dic2[arr[i]] == 0:
		answer += ansar[i]
		dic2[arr[i]] = 1
print(answer)


import sys
import os

def extract(a):
	d = dict()
	r = []
	for e in a:
		if not e in d:
			r.append(1)
			d[e] = d
		else:
			r.append(0)
	return r

def sonyaAndRobots(n, a):
	t1 = extract(a)
	t2 = list(reversed(extract(reversed(a))))
	for i in range(n - 1):
		t1[i + 1] += t1[i]
	result = 0
	for i in range(n - 1):
		result += t1[i] * t2[i + 1]
	return result

def main():
	n = int(input())
	a = [int(x) for x in input().split()]
	print(sonyaAndRobots(n, a))
main()


from collections import Counter
n = int(input())
a = list(map(int, input().split()))
d = Counter(a)
ans = 0
blackset = set(a)
rs = set()
for x in blackset:
	if d[x] > 1:
		ans += 1
ls1 = [n] * 100001
ls2 = [None] * (n + 1)
ls2[n] = 0
i = n - 1
while i >= 0:
	ls2[i] = ls2[i + 1]
	count = ls2[i] - ls2[ls1[a[i]]]
	ans += count
	l = len(rs)
	rs.add(a[i])
	if l < len(rs):
		ls2[i] += 1
	ls1[a[i]] = i
	i -= 1
print(ans)


from collections import deque
n = int(input())
a = list(map(int, input().split()))
ls = deque()
als = set()
for l in range(n - 1):
	if a[l] not in als:
		als.add(a[l])
		ls.append(l)
num_rs = (n + 1) * [0]
ars = set()
for r in reversed(range(1, n)):
	if a[r] not in ars:
		ars.add(a[r])
		num_rs[r] = num_rs[r + 1] + 1
	else:
		num_rs[r] = num_rs[r + 1]
ans = 0
for l in ls:
	ans += num_rs[l + 1]
print(ans)


n = int(input().strip())
numbers = list(map(int, input().strip().split()))
d = {}
d2 = {}
x = [0] * n
x2 = [0] * n
cnt = 0
ans = 0
for i in range(n - 1, -1, -1):
	if numbers[i] in d:
		x[i] = cnt
	else:
		d[numbers[i]] = 1
		cnt += 1
		x[i] = cnt
cnt = 0
for i in range(n):
	if numbers[i] in d2:
		x2[i] = 0
	else:
		d2[numbers[i]] = 1
		cnt += 1
		x2[i] = 1
for i in range(n - 1):
	if x2[i] == 1:
		ans += x[i + 1]
print(ans)


n = int(input())
a = [int(i) for i in input().split()]
c = {}
for r in a:
	if r in c:
		c[r] += 1
	else:
		c[r] = 1
total = 0
b = set()
for i in range(n - 1):
	c[a[i]] -= 1
	if c[a[i]] == 0:
		del c[a[i]]
	if a[i] not in b:
		b.add(a[i])
		total += len(c)
print(total)


n = int(input())
numbers = list(map(int, input().split()))
lefts = set()
rights = set()
uniques = [0 for _ in range(n)]
for i in range(-1, -n - 1, -1):
	uniques[i] = uniques[i + 1]
	if not numbers[i] in rights:
		uniques[i] += 1
		rights.add(numbers[i])
pairs_count = 0
for i in range(n - 1):
	if not numbers[i] in lefts:
		pairs_count += uniques[i + 1]
		lefts.add(numbers[i])
print(pairs_count)


import sys
n = int(sys.stdin.readline())
a = list(map(int, sys.stdin.readline().split()))
arr = [0] * n
suff = set()
for i in range(n - 1, -1, -1):
	suff.add(a[i])
	arr[i] = len(suff)
ans = 0
pre = set()
for i in range(n - 1):
	if a[i] not in pre:
		ans += arr[i + 1]
		pre.add(a[i])
print(ans)


n = int(input())
a = input().split(' ')
for i in range(n):
	a[i] = int(a[i])
lu = {}
for i in range(n):
	lu[a[i]] = []
for i in range(n):
	lu[a[i]].append(i)
mins = []
maxes = []
for val in lu.values():
	mins.append(min(val))
	maxes.append(max(val))
key_num = len(lu.keys())
mins.sort()
maxes.sort()
ind = 0
pairs = 0
counter = key_num
for i in range(len(mins)):
	while maxes[ind] <= mins[i]:
		if ind == len(maxes) - 1:
			counter = 0
			break
		else:
			ind += 1
			counter -= 1
	pairs += counter
print(pairs)


n = int(input())
a = [int(i) for i in input().split()]
d = {}
for i in a:
	d[i] = True
count = 0
b = [0] * (n - 1)
for i in reversed(range(1, n)):
	if d[a[i]]:
		d[a[i]] = False
		count += 1
	b[i - 1] = count
d = {}
for i in a:
	d[i] = True
ans = 0
for i in range(n - 1):
	if d[a[i]]:
		d[a[i]] = False
		ans += b[i]
print(ans)


from __future__ import print_function
import sys
import math
import os.path
import random
from copy import deepcopy
from functools import reduce
from collections import Counter, ChainMap, defaultdict
from itertools import cycle, chain
from queue import Queue, PriorityQueue
from heapq import heappush, heappop, heappushpop, heapify, heapreplace, nlargest, nsmallest
import bisect
from statistics import mean, mode, median, median_low, median_high
sys.setrecursionlimit(10 ** 9)

def log(*args, **kwargs):
	print(*args, file=sys.stderr, **kwargs)

def ni():
	return map(int, input().split())

def nio(offset):
	return map(lambda x: int(x) + offset, input().split())

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

def toString(aList, sep=' '):
	return sep.join((str(x) for x in aList))

def toMapInvertIndex(aList):
	return {k: v for (v, k) in enumerate(aList)}

def sortId(arr):
	return sorted(range(arr), key=lambda k: arr[k])
(n,) = ni()
a = nia()
l = set([])
lc = [0] * n
for i in range(n):
	ax = a[i]
	if i > 0:
		lc[i] = len(l)
	l.add(ax)
r = set([])
count = 0
for i in range(n - 1, -1, -1):
	ar = a[i]
	if ar not in r:
		count += lc[i]
	r.add(ar)
print(count)


n = int(input())
a = list(map(int, input().split()))
d = dict()
for ai in a:
	if ai not in d:
		d[ai] = 0
	d[ai] += 1
l = len(d)
s = set()
ans = 0
for i in range(n):
	ai = a[i]
	if ai not in s:
		s.add(ai)
		d[ai] -= 1
		if d[ai] == 0:
			l -= 1
		ans += l
	else:
		d[ai] -= 1
		if d[ai] == 0:
			l -= 1
print(ans)


n = int(input())
arr = list(map(int, input().split()))
count = 0
d1 = {}
d2 = {}
ans = set()
for i in arr:
	if i in d2.keys():
		d2[i] += 1
	else:
		d2[i] = 1
for i in range(0, n - 1):
	if arr[i] in d1.keys():
		d1[arr[i]] += 1
	else:
		d1[arr[i]] = 1
	d2[arr[i]] -= 1
	if d2[arr[i]] == 0:
		del d2[arr[i]]
	if arr[i] not in ans:
		count += len(d2)
	ans.add(arr[i])
print(count)


noe = int(input())
arr = [int(x) for x in input().split()]
cnt = [0] * int(200000.0)
cur = set()
for x in arr:
	cnt[x] = len(cur)
	cur.add(x)
print(sum(cnt))


n = int(input())
c = [0] * 100001
s = set()
for i in [int(x) for x in input().split()]:
	c[i] = len(s)
	s.add(i)
print(sum(c))


readints = lambda : map(int, input().strip('\n').split())
n = int(input())
nums = list(readints())
cnt = [0] * n
used = {}
i = n - 1
while i >= 0:
	x = nums[i]
	cnt[i] = len(used) - (used[x] if x in used else 0)
	if x not in used:
		used[x] = 0
	used[x] += cnt[i]
	i -= 1
print(sum(cnt))


n = int(input())
s = list(map(int, input().split()))
dic = {}
for i in s:
	dic[i] = len(dic)
print(sum(dic.values()))


import sys, math, bisect
inf = float('inf')
mod = 10 ** 9 + 7

def lcm(a, b):
	return int(a / math.gcd(a, b) * b)

def gcd(a, b):
	return int(math.gcd(a, b))

def tobinary(n):
	return bin(n)[2:]

def binarySearch(a, x):
	i = bisect.bisect_left(a, x)
	if i != len(a) and a[i] == x:
		return i
	else:
		return -1

def lowerBound(a, x):
	i = bisect.bisect_left(a, x)
	if i:
		return i - 1
	else:
		return -1

def upperBound(a, x):
	i = bisect.bisect_right(a, x)
	if i != len(a) + 1 and a[i - 1] == x:
		return i - 1
	else:
		return -1

def primesInRange(n):
	ans = []
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	for p in range(2, n + 1):
		if prime[p]:
			ans.append(p)
	return ans
from collections import deque, defaultdict
for _ in range(1):
	n = int(input())
	arr = list(map(int, input().split()))
	visi = {}
	mp = {}
	for i in arr:
		if i in mp:
			mp[i] += 1
		else:
			mp[i] = 1
	cnt = 0
	for i in range(n - 1):
		x = arr[i]
		if x not in visi:
			if mp[x] > 1:
				cnt += len(mp)
				mp[x] -= 1
				visi[x] = 1
			else:
				del mp[x]
				cnt += len(mp)
				visi[x] = 1
		elif x in mp:
			if mp[x] > 1:
				mp[x] -= 1
			else:
				del mp[x]
	print(cnt)


input()
arr = map(int, input().split())
hash_ = {}
cnt = 0
for x in arr:
	if x not in hash_:
		cnt += len(hash_)
		hash_[x] = len(hash_)
	else:
		cnt += len(hash_) - hash_[x]
		hash_[x] += len(hash_) - hash_[x]
print(cnt)


n = int(input())
s = list(map(int, input().split()))
dist = []
p = [0 for i in range(100005)]
diff = 0
for i in range(n - 1, -1, -1):
	if p[s[i]] == 0:
		p[s[i]] = 1
		diff += 1
	else:
		p[s[i]] += 1
	dist += [diff]
vis = [0 for i in range(100005)]
ans = 0
for i in range(n - 1):
	if vis[s[i]] == 0:
		ans += dist[n - i - 2]
		vis[s[i]] = 1
print(ans)


n = int(input())
A = [int(x) for x in input().split()]
count = 0
freq = [0] * (10 ** 5 + 1)
present = [-1] * (10 ** 5 + 1)
uniq = []
val = 0
for i in range(len(A)):
	uniq.append(val)
	n -= 1
	if freq[A[i]] == 0:
		val += 1
		count += n
	else:
		count -= uniq[present[A[i]]]
	present[A[i]] = i
	freq[A[i]] += 1
print(count)


n = int(input())
a = list(map(int, input().split()))
matrix = [0 for x in range(10 ** 5 + 1)]
run = [0 for x in range(10 ** 5 + 1)]
num = []
c = 0
sumA = 0
for i in range(n - 1):
	run[a[i]] += 1
for j in range(n - 2, -1, -1):
	item = a[j]
	item2 = a[j + 1]
	run[item] -= 1
	if matrix[item2] == 0:
		c += 1
		matrix[item2] = 1
	if run[item] < 1:
		sumA += c
print(sumA)


n = int(input())
A = list(map(int, input().split()))
cnt = [0 for i in range(max(A) + 1)]
B = [1]
cnt[A[0]] = 1
for i in range(1, n):
	if cnt[A[i]] >= 1:
		B.append(B[-1])
		continue
	B.append(B[-1] + 1)
	cnt[A[i]] += 1
B = B[:n - 1]
j = n - 2
ans = 0
mark = [0 for i in range(max(A) + 1)]
while j >= 0:
	if mark[A[j + 1]] == 1:
		j -= 1
		continue
	ans += B[j]
	mark[A[j + 1]] = 1
	j -= 1
print(ans)


n = int(input())
arr = list(map(int, input().split()))
vis = [0] * int(100000.0 + 3)
cnt = [0] * int(100000.0 + 3)
for i in arr:
	vis[i] = 1
	cnt[i] += 1
(res, cnt_distinct) = (0, sum(vis))
for i in arr:
	cnt_distinct -= cnt[i] == 1
	cnt[i] = max(0, cnt[i] - 1)
	if vis[i] == 1:
		res += cnt_distinct
	vis[i] = 0
print(res)


n = int(input())
positions = input().split()
s1 = set()
l1 = [1] * (n - 1)
s2 = set()
l2 = []
count = 0
for i in range(n - 1):
	if positions[i] in s1:
		l1[i] = 0
	s1.add(positions[i])
for i in range(n - 1):
	s2.add(positions[-1 - i])
	l2.append(len(s2))
for i in range(n - 1):
	count += l1[i] * l2[-1 - i]
print(count)


from math import *
import sys
input = sys.stdin.readline

def main():
	n = int(input())
	a = [int(x) for x in input().split(' ')]
	m = {}
	first = {}
	for i in range(len(a)):
		if a[i] not in first:
			first[a[i]] = i
			m[a[i]] = 1
		else:
			m[a[i]] += 1
	cnt = 0
	for i in range(len(a)):
		m[a[i]] -= 1
		if m[a[i]] == 0:
			m.pop(a[i])
		if first[a[i]] == i:
			cnt += len(m)
	print(cnt)
main()


n = int(input())
lst = [int(i) for i in input().split()]
dict = {}
rem_uniq = []
for i in range(n - 1, -1, -1):
	dict[lst[i]] = 1
	rem_uniq.append(len(dict))
dict.clear()
rem_uniq.reverse()
count = 0
for i in range(n - 1):
	if lst[i] in dict:
		continue
	dict[lst[i]] = 1
	count += rem_uniq[i + 1]
print(count)


from collections import Counter
n = int(input())
nums = [int(x) for x in input().split(' ')]
counter = Counter(nums)
visited = set()
total = 0
for i in range(n - 1):
	if counter[nums[i]] == 1:
		del counter[nums[i]]
	else:
		counter[nums[i]] -= 1
	if nums[i] not in visited:
		total += len(counter)
		visited.add(nums[i])
print(total)


n = int(input())
a = [int(j) for j in input().split()]
k = [0] * n
k[n - 1] = 1
s = set()
s.add(a[n - 1])
for i in range(n - 2, -1, -1):
	if a[i] not in s:
		k[i] = k[i + 1] + 1
	else:
		k[i] = k[i + 1]
	s.add(a[i])
s = set()
c = 0
for i in range(n - 1):
	if a[i] not in s:
		c += k[i + 1]
	s.add(a[i])
print(c)


n = int(input())
lst = [*map(int, input().split())]
(a, d, length) = ([], {}, 0)
for (i, x) in enumerate(lst):
	if d.get(x) == None:
		a.append(i)
		d[x] = i
		length += 1
	else:
		d[x] = i
b = list(d.values())
b.sort()
res = 0
from bisect import bisect
for (i, x) in enumerate(a):
	item = bisect(b, x)
	res += length - item
print(res)


n = int(input())
nums = input().split()
dp = [-1] * n
dp[-1] = 0
unique = set()
for i in range(n - 2, -1, -1):
	if nums[i + 1] not in unique:
		unique.add(nums[i + 1])
		dp[i] = len(unique)
	else:
		dp[i] = len(unique)
out = 0
started = set()
for i in range(n):
	if nums[i] not in started:
		out += dp[i]
		started.add(nums[i])
print(out)


import functools
import time

def timer(func):

	@functools.wraps(func)
	def wrapper(*args, **kwargs):
		stime = time.perf_counter()
		res = func(*args, **kwargs)
		elapsed = time.perf_counter() - stime
		print(f'{func.__name__} in {elapsed:.4f} secs')
		return res
	return wrapper

class solver:

	def __init__(self):
		n = int(input())
		a = list(map(int, input().strip().split()))
		MAX = 2 ** 19
		f = [0] * n
		s = set()
		for i in range(n - 1, -1, -1):
			s.add(a[i])
			f[i] = len(s)
		vis = [False] * (MAX + 1)
		ans = 0
		for i in range(n - 1):
			if not vis[a[i]]:
				vis[a[i]] = True
				ans += f[i + 1]
		print(ans)
solver()


n = int(input())
inp = list(map(lambda x: int(x), input().split(' ')))
count = 0
set1 = {inp[0]}
arr = [1]
for i in range(1, n):
	if inp[i] not in set1:
		arr.append(arr[-1] + 1)
		set1.add(inp[i])
	else:
		arr.append(arr[-1])
set2 = {inp[n - 1]}
arr1 = [arr[n - 2]]
for i in range(n - 2, 0, -1):
	if inp[i] not in set2:
		arr1.append(arr[i - 1])
		set2.add(inp[i])
if n != 1:
	print(sum(arr1))
else:
	print(0)


n = int(input())
count = 0
l = tuple(map(int, input().split()))
(start, end) = (dict(), dict())
for i in range(n):
	(start[l[i]], end[l[i]]) = (start.get(l[i], i), i)
(start, end) = (list(sorted(start.values())), list(sorted(end.values())))
for i in start:
	for j in range(len(end)):
		if i < end[j]:
			del end[:j]
			break
	else:
		break
	count += len(end)
print(count)


n = int(input())
L = [int(x) for x in input().split()]
D = {}
Diff = [0]
for i in range(n):
	if L[i] in D:
		D[L[i]].append(i)
		Diff.append(Diff[-1])
	else:
		D[L[i]] = [i]
		Diff.append(Diff[-1] + 1)
ans = 0
for i in range(n - 1, -1, -1):
	if i == D[L[i]][-1]:
		ans += Diff[i]
print(ans)


from collections import defaultdict
n = int(input())
a = list(map(int, input().split()))
counts = defaultdict(int)
for x in a:
	counts[x] += 1
keys = set()
c = len(counts)
ans = 0
for x in a[:-1]:
	if x not in keys:
		keys.add(x)
		counts[x] -= 1
		if counts[x] == 0:
			c -= 1
		ans += c
	else:
		counts[x] -= 1
		if counts[x] == 0:
			c -= 1
print(ans)


def main():
	n = int(input())
	a = tuple(map(int, input().split()))
	seen = set()
	count = 0
	distinct = [0]
	for x in reversed(a):
		if x in seen:
			distinct.append(distinct[-1])
			continue
		seen.add(x)
		distinct.append(distinct[-1] + 1)
	distinct.pop()
	seen.clear()
	for (x, distinct_right) in zip(a, reversed(distinct)):
		if x in seen:
			continue
		seen.add(x)
		count += distinct_right
	print(count)
main()


n = int(input())
l = list(map(int, input().split()))
d = {}
s = set()
for i in l:
	s.add(i)
	if i in d:
		d[i] = d[i] + 1
	else:
		d[i] = 1
cnt = 0
visited = set()
for i in l:
	if i in visited:
		d[i] = d[i] - 1
		if d[i] == 0:
			s.remove(i)
		continue
	else:
		d[i] = d[i] - 1
		visited.add(i)
		if d[i] == 0:
			s.remove(i)
		cnt = cnt + len(s)
print(cnt)


n = int(input())
A = list(map(int, input().split()))
left = [0 for _ in range(10 ** 5 + 1)]
right = [0 for _ in range(10 ** 5 + 1)]
r_non0 = 0
for a in A:
	if right[a] == 0:
		r_non0 += 1
	right[a] += 1
ans = 0
for i in range(n):
	left[A[i]] += 1
	right[A[i]] -= 1
	if right[A[i]] == 0:
		r_non0 -= 1
	if left[A[i]] == 1:
		ans += r_non0
print(ans)


n = int(input())
a = list(map(int, input().split()))
u1 = [100000] * 100001
u2 = [-1] * 100001
for i in range(n):
	u1[a[i]] = min(u1[a[i]], i)
	u2[a[i]] = max(u2[a[i]], i)
st = []
rev = []
for i in range(100001):
	if u1[i] != 100000:
		st += [u1[i]]
	if u2[i] != -1:
		rev += [u2[i]]
st.sort()
rev.sort()
l = 0
ln = len(rev)
ans = 0
for elem in st:
	while l < ln and rev[l] <= elem:
		l += 1
	ans += ln - l
print(ans)


n = int(input())
a = input().split(' ')
d = {}
t = {}
amount = 0
for i in range(n):
	a[i] = int(a[i])
	elem = a[i]
	if elem not in d.keys():
		d[elem] = 1
		t[elem] = 1
		amount += 1
	else:
		d[elem] += 1
		t[elem] += 1
pairs = 0
for i in range(n - 1):
	if d[a[i]] == t[a[i]]:
		d[a[i]] -= 1
		if d[a[i]] == 0:
			amount -= 1
		pairs += amount
	else:
		d[a[i]] -= 1
		if d[a[i]] == 0:
			amount -= 1
print(pairs)


n = int(input())
s = [int(i) for i in input().strip().split()]
processed = set()
seen = set()
rightSetLength = [0 for i in range(100000)]
sum = 0
rightSetLength[len(s) - 1] = 1
seen.add(s[len(s) - 1])
for i in range(len(s) - 2, 0, -1):
	if not s[i] in seen:
		rightSetLength[i] = rightSetLength[i + 1] + 1
		seen.add(s[i])
	else:
		rightSetLength[i] = rightSetLength[i + 1]
for i in range(0, len(s) - 1):
	if not s[i] in processed:
		sum = sum + rightSetLength[i + 1]
		processed.add(s[i])
print(sum)


from collections import defaultdict
from bisect import bisect
INF = 10 ** 9
n = int(input())
a = list(map(int, input().split()))
first_pos = [INF] * (n + 1)
for (i, x) in enumerate(a):
	if first_pos[x] == INF:
		first_pos[x] = i
last_pos = [-1] * (n + 1)
for (i, x) in enumerate(a):
	last_pos[x] = i
last_pos.sort()
total = 0
for (i, first) in enumerate(first_pos):
	total += len(last_pos) - bisect(last_pos, first)
print(total)


n = int(input())
a = list(map(int, input().split()))
kol_left_on_right = {}
for x in a:
	kol_left_on_right[x] = len(kol_left_on_right)
print(sum(kol_left_on_right.values()))


n = int(input())
a = [int(x) for x in input().split()]
s = set()
d = dict()
c = [0] * n
for i in range(n - 1, -1, -1):
	c[i] = len(s)
	s.add(a[i])
	d[a[i]] = i
ans = 0
for k in d.keys():
	pos = d[k]
	ans += c[pos]
print(ans)


from collections import defaultdict
n = int(input())
arr = list(map(int, input().split()))
list1 = [False] * (10 ** 5 + 1)
d = defaultdict(int)
count = 0
for i in range(n):
	d[arr[i]] += 1
for i in range(n - 1):
	d[arr[i]] -= 1
	if d[arr[i]] == 0:
		del d[arr[i]]
	if list1[arr[i]] == False:
		count += len(d.items())
		list1[arr[i]] = True
print(count)


import sys
import bisect
from collections import deque
Ri = lambda : [int(x) for x in sys.stdin.readline().split()]
ri = lambda : sys.stdin.readline().strip()

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

def list2d(a, b, c):
	return [[c] * b for i in range(a)]

def list3d(a, b, c, d):
	return [[[d] * c for j in range(b)] for i in range(a)]

def list4d(a, b, c, d, e):
	return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]

def ceil(x, y=1):
	return int(-(-x // y))

def INT():
	return int(input())

def MAP():
	return map(int, input().split())

def LIST(N=None):
	return list(MAP()) if N is None else [INT() for i in range(N)]

def Yes():
	print('Yes')

def No():
	print('No')

def YES():
	print('YES')

def NO():
	print('NO')
INF = 10 ** 18
MOD = 10 ** 9 + 7
n = int(ri())
a = Ri()
u = [0] * (n + 1)
s = set()
for i in range(n - 1, -1, -1):
	u[i] = len(s)
	s.add(a[i])
s = set()
ans = 0
for i in range(len(a)):
	if a[i] not in s:
		ans += u[i]
		s.add(a[i])
print(ans)


import sys, os, io
import math, bisect, operator
(inf, mod) = (float('inf'), 10 ** 9 + 7)
from itertools import groupby, accumulate
from heapq import heapify, heappop, heappush
from collections import deque, Counter, defaultdict
input = iter(sys.stdin.buffer.read().decode().splitlines()).__next__
Neo = lambda : list(map(int, input().split()))
(n,) = Neo()
A = Neo()
B = [0] * (n + 1)
s = set()
for i in range(n - 1, -1, -1):
	if A[i] not in s:
		B[i] += 1 + B[i + 1]
	else:
		B[i] = B[i + 1]
	s.add(A[i])
s = set()
Ans = 0
for i in range(n):
	if A[i] not in s:
		Ans += B[i + 1]
	s.add(A[i])
print(Ans)


input()
N = 100001
c = [0] * N
s = [1] * N
l = 0
for x in map(int, input().split()):
	c[x] = l
	if s[x]:
		l += 1
		s[x] = 0
print(sum(c))


import functools
import time

def timer(func):

	@functools.wraps(func)
	def wrapper(*args, **kwargs):
		stime = time.perf_counter()
		res = func(*args, **kwargs)
		elapsed = time.perf_counter() - stime
		print(f'{func.__name__} in {elapsed:.4f} secs')
		return res
	return wrapper

class solver:

	def __init__(self):
		n = int(input())
		a = list(map(int, input().strip().split()))
		MAX = 2 ** 19
		fen = [0] * (MAX + 1)
		vis = [False] * (MAX + 1)
		dl = [n] * (MAX + 1)
		dr = [n] * (MAX + 1)
		for i in range(n):
			dl[a[i]] = min(dl[a[i]], i)
		for i in range(n - 1, -1, -1):
			dr[a[i]] = min(dr[a[i]], n - 1 - i)

		def inc(p, val):
			p += 1
			while p <= MAX:
				fen[p] += val
				p += p & -p

		def query(p):
			p += 1
			res = 0
			while p > 0:
				res += fen[p]
				p -= p & -p
			return res
		for i in range(n - 1):
			val = dl[a[i]]
			if not vis[val]:
				inc(val, 1)
				vis[val] = True
		ans = 0
		vis = [False] * (MAX + 1)
		for i in range(n - 1, 0, -1):
			if not vis[a[i]]:
				q = max(0, n - 2 - dr[a[i]])
				ans += query(q)
				vis[a[i]] = True
		print(ans)
solver()


n = int(input())
l = list(map(int, input().split()))
maxl = max(l) + 1
dp = []
for i in range(maxl):
	dp.append([-1, -1])
for i in range(n):
	dp[l[i]][1] = i
for i in range(n - 1, -1, -1):
	dp[l[i]][0] = i
ll = []
lr = []
for i in range(n):
	ll.append(0)
	lr.append(0)
cnt = 0
for i in range(maxl):
	if dp[i][0] != -1:
		ll[dp[i][0]] = 1
		lr[dp[i][1]] = 1
		cnt += 1
ans = 0
for i in range(n):
	if lr[i] == 1:
		cnt -= 1
	if ll[i] == 1:
		ans += cnt
print(ans)


from sys import stdin

def solution(elems):
	n = len(elems)
	count = 0
	unique_elems = set()
	unique_elems_count = [0] * n
	unique_elems_count[n - 1] = 0
	for i in range(n - 2, -1, -1):
		unique_elems_count[i] = 1 + unique_elems_count[i + 1] if elems[i + 1] not in unique_elems else unique_elems_count[i + 1]
		unique_elems.add(elems[i + 1])
	previous_seen = set()
	for i in range(len(elems)):
		if elems[i] in previous_seen:
			continue
		else:
			count += unique_elems_count[i]
			previous_seen.add(elems[i])
	return count

def main():
	_ = int(stdin.readline().strip())
	elems = list(map(int, stdin.readline().split()))
	print(solution(elems))
main()


n = int(input())
a = list(map(int, input().split()))
c = set(a)
cl = len(c)
from collections import defaultdict
d = defaultdict(int)
for (i, ai) in enumerate(a):
	d[ai] += 1
s = 0
v = set()
for ai in a:
	d[ai] -= 1
	if d[ai] == 0:
		c.remove(ai)
	if ai in v:
		continue
	v.add(ai)
	s += len(c)
print(s)


n = int(input())
a = [int(item) for item in input().split()]
different = [0] * n
different[n - 1] = 0
already = {key: 0 for key in a}
for i in range(n - 2, -1, -1):
	different[i] = different[i + 1] + 1 - already[a[i + 1]]
	already[a[i + 1]] = 1
done = {key: 0 for key in a}
ans = 0
for i in range(n):
	if done[a[i]]:
		continue
	done[a[i]] = 1
	ans += different[i]
print(ans)


n = int(input())
t = list(map(int, input().split()))
uj = [False] * n
bvolt = [False] * 100008
jvolt = [False] * 100008
for i in range(n):
	if not bvolt[t[i]]:
		bvolt[t[i]] = True
		uj[i] = True
cnt = 0
ans = 0
for i in range(n - 1, 0, -1):
	if not jvolt[t[i]]:
		jvolt[t[i]] = True
		cnt += 1
	if uj[i - 1]:
		ans += cnt
print(ans)


n = int(input())
v = [False] * 100001
g = 0
o = g * 2
kor = [False] * n
plus = [False] * n
r = [int(i) for i in input().split()]
for i in range(n):
	if v[r[i]] == False:
		kor[i] = True
		g += 1
		v[r[i]] = True
v = [False] * 100001
for i in range(n):
	if v[r[n - i - 1]] == False:
		plus[n - i - 1] = True
		v[r[n - i - 1]] = True
for i in range(n):
	if plus[i] == True:
		g -= 1
	if kor[i] == True:
		o += g
print(o)


input()
num = {}
for i in list(map(int, input().split())):
	num[i] = len(num)
print(sum(num.values()))


from sys import stdin, stdout
import math, bisect
from collections import Counter, deque, defaultdict
L = lambda : list(map(int, stdin.readline().strip().split()))
M = lambda : map(int, stdin.readline().strip().split())
I = lambda : int(stdin.readline().strip())
S = lambda : stdin.readline().strip()
C = lambda : stdin.readline().strip().split()

def pr(a):
	return ''.join(list(map(str, a)))

def solve():
	n = I()
	a = L()
	s = set()
	ans = [0] * (10 ** 5 + 5)
	for i in a:
		ans[i] = len(s)
		s.add(i)
	print(sum(ans))
for _ in range(1):
	solve()


n = int(input())
l = [int(el) for el in input().split()]
col = 0
a = [0] * 100001
s = set()
for i in range(n):
	if a[l[i]] == 0:
		col += len(s)
		a[l[i]] += len(s)
		s.add(l[i])
	else:
		col += len(s) - a[l[i]]
		a[l[i]] = len(s)
		s.add(l[i])
print(col)


n = int(input())
numbers = list(map(int, input().split(' ')))
twice_numbers = []
occurences = {}
for i in numbers:
	if i in occurences.keys():
		occurences[i] += 1
	else:
		occurences[i] = 1
occurence = {}
for i in numbers:
	if i in occurence.keys():
		occurence[i] += 1
	else:
		occurence[i] = 1
	if occurence[i] == 1 or occurence[i] == occurences[i]:
		twice_numbers.append(i)
double = {i for (i, n) in occurences.items() if n >= 2}
used = set()
count = 0
for (i, m) in enumerate(twice_numbers):
	if m not in used:
		if m in double:
			double.remove(m)
		count += len(twice_numbers) - len(double) - i - 1
		used.add(m)
print(count)


import os
import collections

def sonya_and_robots():
	c = collections.Counter(arr)
	cou = 0
	unique = set()
	for ele in arr:
		if c[ele] > 1:
			c[ele] = c[ele] - 1
		else:
			del c[ele]
		if ele not in unique:
			cou += len(c)
			unique.add(ele)
	return cou
size = input()
arr = list(map(int, input().split()))
print(sonya_and_robots())


n = int(input())
s = list(map(int, list(input().split())))[0:n]
l = {}
r = {}
f = [0 for i in range(n + 1)]
tmp = 0
for i in range(n):
	x = l.get(s[i], -1)
	if x == -1:
		l[s[i]] = 1
		tmp += 1
	f[i + 1] = tmp
g = [0 for i in range(n + 1)]
tmp = 0
for i in range(n):
	x = r.get(s[n - 1 - i], -1)
	if x == -1:
		r[s[n - 1 - i]] = 1
		tmp += 1
	g[n - 1 - i] = tmp
res = 0
for i in range(1, n):
	res += (f[i] - f[i - 1]) * g[i]
print(res)


input()
a = [int(x) for x in input().split()]
d = {}
for i in a:
	d[i] = len(d)
print(sum(d.values()))


n = int(input())
u = list(map(int, input().split()))
ans = 0
use = set()
s = set()
u_len = [0] * n
for i in range(n - 1, 0, -1):
	if u[i] not in s:
		s.add(u[i])
		u_len[i - 1] = u_len[i] + 1
	else:
		u_len[i - 1] = u_len[i]
for i in range(n):
	if u[i] not in use:
		use.add(u[i])
		ans += u_len[i]
print(ans)


n = int(input())
a = list(map(int, input().split()))
left = [0] * n
right = [0] * n
num = [0] * (10 ** 5 + 1)
num_2 = [0] * (10 ** 5 + 1)
bal = 0
for i in range(n):
	if num[a[i]] == 0:
		num[a[i]] = 1
		left[i] = 1
	i += 1
	if num_2[a[n - i]] == 0:
		num_2[a[n - i]] = 1
		right[n - i] = 1
		bal += 1
cnt = 0
for u in range(n):
	if right[u] == 1:
		bal -= 1
	if left[u] == 1:
		cnt += bal
print(cnt)


n = int(input())
nums = list(map(int, input().split()))
left = {}
for i in range(n):
	if nums[i] in left.keys():
		left[nums[i]] += 1
	else:
		left[nums[i]] = 1
count = 0
done = set()
for i in nums:
	left[i] -= 1
	if left[i] == 0:
		del left[i]
	if i not in done:
		count += len(left.keys())
		done.add(i)
print(count)


n = int(input())
a = [int(i) for i in input().split()]
from_r = [0] * n
st = set()
for i in range(n - 1, -1, -1):
	st.add(a[i])
	from_r[i] = len(st)
if n == 1:
	exit(print(0))
st.clear()
ans = 0
for i in range(n - 1):
	if a[i] in st:
		continue
	st.add(a[i])
	ans += from_r[i + 1]
print(ans)


import sys
n = int(sys.stdin.readline())
a = sys.stdin.readline().split()
rem = {}
used = set()
for v in a:
	if v not in rem:
		rem[v] = 1
	else:
		rem[v] = rem[v] + 1
ans = 0
for v in a:
	rem[v] = rem[v] - 1
	if rem[v] == 0:
		del rem[v]
	if v in used:
		continue
	ans = ans + len(rem)
	used.add(v)
print(ans)


n = int(input())
a = list(map(int, input().split(' ')))
if n == 1:
	print(0)
	exit()
a.reverse()
z = []
s = set()
s.add(a[0])
b = {a[0]: 0}
for i in range(1, n):
	if a[i] in s:
		b[a[i]] = len(s)
	else:
		b.update({a[i]: len(s)})
		s.add(a[i])
ans = 0
for i in b.keys():
	ans += b[i]
print(ans)


def readList(converter=int):
	return [converter(x) for x in input().strip().split()]
(n,) = readList()
l = readList()
uniq = set()
uniqRight = [0 for _ in range(n)]
uniqRight[len(uniqRight) - 1] = 0
for i in reversed(range(n - 1)):
	uniqRight[i] = uniqRight[i + 1] + (1 if l[i + 1] not in uniq else 0)
	uniq.add(l[i + 1])
counts = 0
uniq = set()
for i in range(n):
	if l[i] not in uniq:
		counts += uniqRight[i]
	uniq.add(l[i])
print(counts)


n = int(input())
A = list(map(int, input().split()))
res_set = set()
tmp_set = set()
NumList = [0 for i in range(n)]
for i in range(n - 1, -1, -1):
	tmp_set.add(A[i])
	NumList[i] = len(tmp_set)
ans = 0
for i in range(n - 1):
	if not A[i] in res_set:
		res_set.add(A[i])
		ans += NumList[i + 1]
print(ans)


def i_ints():
	return map(int, input().split())
(n,) = i_ints()
a = list(i_ints())
seen = set()
seen_count = []
for x in a:
	seen.add(x)
	seen_count.append(len(seen))
count = 0
seen = set()
for i in range(n - 1, 0, -1):
	if a[i] not in seen:
		seen.add(a[i])
		count += seen_count[i - 1]
print(count)


def readints():
	return [int(x) for x in input().strip().split()]

def main():
	n = readints()[0]
	a = readints()
	pre = [0] * (n + 1)
	pre[n - 1] = 1
	s = set()
	s.add(a[n - 1])
	for i in range(1, n):
		pre[n - i - 1] = pre[n - i] + (a[n - i - 1] not in s)
		s.add(a[n - i - 1])
	ans = 0
	s = set()
	for i in range(n):
		if a[i] not in s:
			ans += pre[i + 1]
		s.add(a[i])
	print(ans)
main()


from collections import Counter
n = int(input())
a = list(map(int, input().split()))
d = Counter(a)
visited = set()
res = 0
for i in range(n):
	d[a[i]] -= 1
	if d[a[i]] == 0:
		del d[a[i]]
	if a[i] in visited:
		continue
	visited.add(a[i])
	res += len(d)
print(res)


n = int(input())
a = [int(i) for i in input().split()]
d = {}
s = set()
for i in a:
	if d.get(i):
		d[i] += 1
	else:
		d[i] = 1
ans = 0
for i in a:
	d[i] -= 1
	if d[i] == 0:
		d.pop(i)
	if i not in s:
		ans += len(d.keys())
	s.add(i)
print(ans)


n = int(input())
arr = list(map(int, input().split()))
rightset = set(arr[1:])
rel = len(rightset)
rarr = [0] * 100001
for i in range(1, n):
	rarr[arr[i]] += 1
lset = set('0')
lset.clear()
lset.add(arr[0])
lel = 1
ans = rel
for i in range(1, n - 1):
	f = False
	q = arr[i]
	lset.add(q)
	if len(lset) > lel:
		f = True
		lel += 1
	rarr[q] -= 1
	if rarr[q] == 0:
		rel -= 1
	if f:
		ans += rel
print(ans)


import math, sys, bisect, heapq
from collections import defaultdict, Counter, deque
from itertools import groupby, accumulate
from functools import lru_cache
int1 = lambda x: int(x) - 1
input = iter(sys.stdin.buffer.read().decode().splitlines()).__next__
aj = lambda : list(map(int, input().split()))

def list3d(a, b, c, d):
	return [[[d] * c for j in range(b)] for i in range(a)]

def Y(c):
	print(['NO', 'YES'][c])

def y(c):
	print(['no', 'yes'][c])

def Yy(c):
	print(['No', 'Yes'][c])
(n,) = aj()
A = aj()
g = [i for i in A]
s = set()
suf = []
c = 0
mark = {}
for i in range(len(g) - 1, -1, -1):
	if g[i] not in s:
		c += 1
		s.add(g[i])
	suf.append(c)
suf = suf[::-1]
ans = 0
ok = set()
for i in range(len(g) - 1):
	if g[i] not in ok:
		ok.add(g[i])
		ans += suf[i + 1]
print(ans)


n = int(input())
nums = [int(i) for i in input().strip().split()]
distinctRight = set()
right = [0] * n
for i in range(n - 1, -1, -1):
	right[i] = len(distinctRight)
	distinctRight.add(nums[i])
assigned = set()
ans = 0
for i in range(n):
	if nums[i] not in assigned:
		ans += right[i]
		assigned.add(nums[i])
print(ans)


n = int(input())
arr = [int(i) - 1 for i in input().split()]
was = [int(0) for i in range(10 ** 5)]
was2 = [int(0) for i in range(10 ** 5)]
cnt = 0
for i in arr:
	was[i] += 1
	if was[i] == 1:
		cnt += 1
ans = 0
for i in arr:
	was[i] -= 1
	if was[i] == 0:
		cnt -= 1
	if was2[i] != 0:
		continue
	was2[i] = 1
	ans += cnt
print(ans)


import sys
import math
from collections import defaultdict, deque
input = sys.stdin.readline

def inar():
	return [int(el) for el in input().split()]

def main():
	n = int(input())
	arr = inar()
	dic = {}
	dp = [0] * n
	count = 0
	for i in range(n - 1, -1, -1):
		if arr[i] not in dic:
			dic[arr[i]] = 1
			count += 1
		dp[i] = count
	ans = 0
	check = set()
	for i in range(n - 1):
		if arr[i] not in check:
			ans += dp[i + 1]
			check.add(arr[i])
	print(ans)
main()


input()
dc = {}
for i in map(int, input().split()):
	dc[i] = len(dc)
print(sum(dc.values()))


import sys
lines = []
for line in sys.stdin:
	lines.append(line)
parsed = lines[1].split()
values = list(map(lambda x: int(x), parsed))
unique_values = set()
unique_values_count = []
for item in reversed(values):
	unique_values.add(item)
	unique_values_count.append(len(unique_values))
unique_values_count = list(reversed(unique_values_count))
pairs = 0
values_first_in_pair = set()
for index in range(len(values) - 1):
	item = values[index]
	if item in values_first_in_pair:
		continue
	values_first_in_pair.add(item)
	pairs = pairs + unique_values_count[index + 1]
print(pairs)


cnt = int(input())
data = [int(x) for x in input().split()]
totalSolutions = 0
tset1 = set([data[-1]])
data2 = []
aug = data[:]
aug[-1] = 1
for x in range(-2, -len(data) - 1, -1):
	if data[x] not in tset1:
		tset1.add(data[x])
		aug[x] = aug[x + 1] + 1
	else:
		aug[x] = aug[x + 1]
s = set(data[:])
tset2 = set([])
for i in range(0, len(data)):
	if data[i] not in tset2:
		if i < len(data) - 1:
			totalSolutions += aug[i + 1]
			tset2.add(data[i])
print(totalSolutions)


n = int(input())
a = list(map(int, input().split()))
right = list()
s = set()
for el in a[::-1]:
	s.add(el)
	right.append(len(s))
right = right[::-1]
s = set()
ans = 0
for (i, el) in enumerate(a[:-1]):
	if el not in s:
		ans += right[i + 1]
	s.add(el)
print(ans)


n = int(input())
a = list(map(int, input().split()))
dic = {}
for i in range(len(a) - 1):
	if a[i] not in dic:
		dic[a[i]] = 1
	else:
		dic[a[i]] += 1
been = set([])
cnt = 0
for i in range(len(a) - 1, 0, -1):
	if a[i] not in been:
		cnt += len(dic)
		been.add(a[i])
	dic[a[i - 1]] -= 1
	if dic[a[i - 1]] == 0:
		del dic[a[i - 1]]
print(cnt)


n = int(input())
l = list(map(int, input().split()))
c = [0] * 100001
s = set()
for i in l:
	c[i] = len(s)
	s.add(i)
print(sum(c))


n = int(input())
a = list(map(int, input().split()))
ans = 0
vis = set()
dp = [0] * (n + 1)
for i in reversed(range(n)):
	vis.add(a[i])
	dp[i] = len(vis)
vis.clear()
for (i, x) in enumerate(a):
	if x in vis:
		continue
	vis.add(x)
	ans += dp[i + 1]
print(ans)


n = int(input())
aa = list(map(int, input().split(' ')))
us = [0] * (n + 1)
cur = set()
for (i, a) in enumerate(aa):
	cur.add(a)
	us[i + 1] = len(cur)
res = 0
used = set()
for (i, a) in reversed(list(enumerate(aa))):
	if a not in used:
		used.add(a)
		res += us[i]
print(res)


from bisect import *
n = int(input())
N = 100001
l = [N] * N
r = [-1] * N
for (i, x) in enumerate(map(int, input().split())):
	l[x] = min(l[x], i)
	r[x] = max(r[x], i)
l.sort()
print(sum((bisect_left(l, x) for x in r)))


def main():
	n = int(input())
	a = list(map(int, input().split()))
	uniques = [0] * (n - 1) + [1]
	bools = [True] * 100001
	bools2 = [True] * 100001
	bools[a[-1]] = False
	for i in range(n - 2, 0, -1):
		temp = 0
		if bools[a[i]]:
			bools[a[i]] = False
			temp = 1
		uniques[i] = uniques[i + 1] + temp
	ret = 0
	for i in range(n - 1):
		if bools2[a[i]]:
			bools2[a[i]] = False
			ret += uniques[i + 1]
	print(ret)
	return 0
main()


n = int(input())
arr = list(map(int, input().split()))
ans = 0
dic = {}
k = set([arr[-1]])
for i in range(2, n + 1):
	dic[arr[-i]] = len(k)
	k.add(arr[-i])
print(sum(dic.values()))


from sys import stdin, stdout
nmbr = lambda : int(stdin.readline())
lst = lambda : list(map(int, stdin.readline().split()))
for _ in range(1):
	n = nmbr()
	a = lst()
	cnt = ans = 0
	d = [0] * (10 ** 5 + 5)
	vis = set()
	for v in a:
		d[v] += 1
	for v in d:
		if v != 0:
			cnt += 1
	for i in range(n):
		d[a[i]] -= 1
		if d[a[i]] == 0:
			cnt -= 1
		if a[i] in vis:
			continue
		ans += cnt
		vis.add(a[i])
	print(ans)


n = int(input())
a = list(map(int, input().split()))
cnt = [0] * (n + 1)
used = [0] * 100001
for i in range(n - 1, 0, -1):
	cnt[i] = cnt[i + 1]
	if used[a[i]] == 0:
		cnt[i] += 1
		used[a[i]] = 1
ans = 0
vis = [0] * 100001
for i in range(n - 1):
	if vis[a[i]] == 0:
		ans += cnt[i + 1]
		vis[a[i]] = 1
print(ans)


n = int(input())
a = [int(x) for x in input().split()]
st = set(a)
tot = len(st)
freq = [0 for _ in range(100005)]
used = [0 for _ in range(100005)]
for x in a:
	freq[x] += 1
res = sum((freq[x] > 1 for x in st))
for x in a:
	freq[x] -= 1
	if freq[x] == 0:
		tot -= 1
	if used[x] == 0:
		res += tot - (freq[x] > 0)
	used[x] = 1
print(res)


n = int(input())
a = [int(x) for x in input().split()]
b = [0] * n
s = set()
for i in range(n - 1, -1, -1):
	if a[i] not in s:
		s.add(a[i])
		b[i] = 1
r = 0
s = set()
for i in range(n):
	if b[i]:
		r += len(s)
	s.add(a[i])
print(r)