Parmida is a clever girl and she wants to participate in Olympiads this year. Of course she wants her partner to be clever too (although he's not)! Parmida has prepared the following test problem for Pashmak.

There is a sequence a that consists of n integers a_1, a_2, ..., a_{n}. Let's denote f(l, r, x) the number of indices k such that: l ≤ k ≤ r and a_{k} = x. His task is to calculate the number of pairs of indicies i, j (1 ≤ i < j ≤ n) such that f(1, i, a_{i}) > f(j, n, a_{j}).

Help Pashmak with the test.


-----Input-----

The first line of the input contains an integer n (1 ≤ n ≤ 10^6). The second line contains n space-separated integers a_1, a_2, ..., a_{n} (1 ≤ a_{i} ≤ 10^9).


-----Output-----

Print a single integer — the answer to the problem.


-----Examples-----
Input
7
1 2 1 1 2 2 1

Output
8

Input
3
1 1 1

Output
1

Input
5
1 2 3 4 5

Output
0

Source: codeforces | Difficulty: MEDIUM_HARD
Tags: Sorting

Data structures

Divide and conquer


Solutions:
import sys
input = sys.stdin.readline
BIT = [0] * 10 ** 6

def update(idx):
	while idx < len(BIT):
		BIT[idx] += 1
		idx += idx & -idx

def query(idx):
	s = 0
	while idx > 0:
		s += BIT[idx]
		idx -= idx & -idx
	return s
n = int(input())
a = list(map(int, input().split()))
ans = 0
cnt = {}
l = [0] * n
r = [0] * n
for i in range(n):
	cnt[a[i]] = cnt.get(a[i], 0) + 1
	l[i] = cnt[a[i]]
cnt.clear()
for i in range(n)[::-1]:
	cnt[a[i]] = cnt.get(a[i], 0) + 1
	r[i] = cnt[a[i]]
	if i < n - 1:
		ans += query(l[i] - 1)
	update(r[i])
print(ans)


import sys
input = sys.stdin.readline
for _ in range(1):
	n = int(input())
	arr = [int(x) for x in input().split()]
	b = [0 for i in range(n + 1)]

	def update(i, val, n):
		i += 1
		while i < n:
			b[i] += val
			i += i & -i
		return

	def get(i):
		i += 1
		ans = 0
		while i > 0:
			ans += b[i]
			i -= i & -i
		return ans
	d = {}
	for i in arr:
		if i in d:
			d[i] += 1
		else:
			d[i] = 1
		update(d[i], 1, n + 1)
	ans = 0
	now = {}
	for i in arr:
		update(d[i], -1, n + 1)
		d[i] -= 1
		if i in now:
			now[i] += 1
		else:
			now[i] = 1
		ans += get(now[i] - 1)
	print(ans)


INF = 10 ** 10

def merge(l, r):
	res = l + r
	i = j = k = 0
	while i < len(l) and j < len(r):
		if l[i] < r[j]:
			res[k] = l[i]
			k += 1
			i += 1
		else:
			res[k] = r[j]
			k += 1
			j += 1
	while i < len(l):
		res[k] = l[i]
		k += 1
		i += 1
	while j < len(r):
		res[k] = r[j]
		k += 1
		j += 1
	return res

def solve(fl, fr, l, r):
	if l == r:
		return 0
	mid = (l + r) // 2
	res = solve(fl, fr, l, mid) + solve(fl, fr, mid + 1, r)
	(i, j) = (l, mid + 1)
	while i <= mid:
		while j <= r and fr[j] < fl[i]:
			j += 1
		res += j - mid - 1
		i += 1
	fl[l:r + 1] = merge(fl[l:mid + 1], fl[mid + 1:r + 1])
	fr[l:r + 1] = merge(fr[l:mid + 1], fr[mid + 1:r + 1])
	return res
n = int(input())
a = list(map(int, input().split()))
(fl, cnt) = ([], {})
for x in a:
	cnt[x] = cnt.get(x, 0) + 1
	fl.append(cnt[x])
(fr, cnt) = ([], {})
for x in a[::-1]:
	cnt[x] = cnt.get(x, 0) + 1
	fr.append(cnt[x])
fr = fr[::-1]
print(solve(fl, fr, 0, n - 1))


n = int(input())

def getsum(BITTree, i):
	s = 0
	i = i + 1
	while i > 0:
		s += BITTree[i]
		i -= i & -i
	return s

def updatebit(BITTree, n, i, v):
	i += 1
	while i <= n:
		BITTree[i] += v
		i += i & -i
a = list(map(int, input().split()))
pre = dict()
pos = dict()
for i in range(n):
	if pre.get(a[i], None) == None:
		pre[a[i]] = 0
	pre[a[i]] += 1
ans = 0
BIT = [0] * (n + 1)
for i in range(n - 1, 0, -1):
	pre[a[i]] -= 1
	if pos.get(a[i], None) == None:
		pos[a[i]] = 0
	pos[a[i]] += 1
	updatebit(BIT, n, pos[a[i]], 1)
	temp = getsum(BIT, pre[a[i - 1]] - 1)
	ans += temp
print(ans)


import sys
import io
import math
import collections
import decimal
import itertools
import bisect
import heapq

def input():
	return sys.stdin.readline()[:-1]

class BIT:

	def __init__(self, n):
		self.size = n
		self.data = [0] * (n + 1)

	def add(self, i, x):
		while i <= self.size:
			self.data[i] += x
			i += i & -i

	def get_sum(self, i):
		s = 0
		while i > 0:
			s += self.data[i]
			i -= i & -i
		return s
N = int(input())
A = list(map(int, input().split()))
N1 = 2 ** (N - 1).bit_length()
Dat = [0] * (2 * N1)
D = {a: i for (i, a) in enumerate(sorted(set(A)))}
B = [D[a] for a in A]
Count1 = [0] * N
T1 = [list() for _ in range(N)]
for i in range(N):
	v = Count1[B[i]]
	T1[v].append(i)
	Count1[B[i]] += 1
Count2 = [0] * N
T2 = [list() for _ in range(N)]
for i in reversed(range(N)):
	v = Count2[B[i]]
	T2[v].append(i)
	Count2[B[i]] += 1
ans = 0
bit = BIT(N)
for i in range(1, N):
	for k in T2[i - 1]:
		bit.add(N - k, 1)
	for l in T1[i]:
		n = bit.get_sum(N - 1 - l)
		ans += n
print(ans)


tree = [0] * 10 ** 6

def update(index):
	while index < len(tree):
		tree[index] += 1
		index += index & -index

def query(index):
	s = 0
	while index > 0:
		s += tree[index]
		index -= index & -index
	return s
n = int(input())
a = list(map(int, input().split()))
ans = 0
count = {}
left = [0] * n
right = [0] * n
for i in range(n):
	count[a[i]] = count.get(a[i], 0) + 1
	left[i] = count[a[i]]
count.clear()
for i in range(n - 1, -1, -1):
	count[a[i]] = count.get(a[i], 0) + 1
	right[i] = count[a[i]]
	if i < n - 1:
		ans += query(left[i] - 1)
	update(right[i])
print(ans)


import sys

def update(i, val):
	while i < maxi:
		bit[i] += val
		i += i & -i

def query(i):
	ans = 0
	while i > 0:
		ans += bit[i]
		i -= i & -i
	return ans
from collections import defaultdict
n = int(input())
l = list(map(int, sys.stdin.readline().split()))
bit = [0 for i in range(n + 30)]
maxi = n + 20
one_to_i = []
d = defaultdict(int)
for i in range(n - 1):
	d[l[i]] += 1
	one_to_i.append(d[l[i]])
one_to_i = one_to_i[::-1]
j_to_n = []
d2 = defaultdict(int)
for i in range(n - 1, 0, -1):
	d2[l[i]] += 1
	j_to_n.append(d2[l[i]])
ans = 0
for i in range(n - 1):
	update(j_to_n[i], 1)
	ans += query(one_to_i[i] - 1)
print(ans)


from sys import stdin, stdout

class bit:

	def __init__(self, n):
		self.n = n
		self.f = [0] * (n + 1)

	def update(self, pos, value):
		while pos <= self.n:
			self.f[pos] += value
			pos += pos & -pos

	def sum(self, pos):
		res = 0
		while pos:
			res += self.f[pos]
			pos -= pos & -pos
		return res

def unique(A):
	C = sorted(A)
	B = []
	for element in C:
		if not B or B[-1] != element:
			B.append(element)
	return B
n = int(stdin.readline())
A = [int(x) for x in stdin.readline().split()]
Atmp = [0] * n
Work = bit(n + 10)
Map = {}
for index in range(n - 1, -1, -1):
	if A[index] in Map:
		Map[A[index]] += 1
	else:
		Map[A[index]] = 1
	Atmp[index] = Map[A[index]]
	Work.update(Map[A[index]], 1)
Map.clear()
ans = 0
for i in range(n):
	if A[i] in Map:
		Map[A[i]] += 1
	else:
		Map[A[i]] = 1
	Work.update(Atmp[i], -1)
	ans += Work.sum(Map[A[i]] - 1)
stdout.write('%d' % ans)


from collections import defaultdict
total = 0

def update(ft, pos, val):
	global total
	total += 1
	while pos < len(ft):
		ft[pos] += val
		pos += pos & -pos

def query(ft, pos):
	ans = 0
	while pos > 0:
		ans += ft[pos]
		pos -= pos & -pos
	return ans
n = int(input())
arr = list(map(lambda x: int(x), input().split()))
freCount = defaultdict(int)
leftCount = []
rightCount = []
ans = 0
ft = [0] * (n + 10)
for i in range(n):
	if arr[i] in freCount:
		freCount[arr[i]] += 1
	else:
		freCount[arr[i]] = 1
	leftCount.append(freCount[arr[i]])
freCount = defaultdict(int)
for i in range(n - 1, -1, -1):
	if arr[i] in freCount:
		freCount[arr[i]] += 1
	else:
		freCount[arr[i]] = 1
	update(ft, freCount[arr[i]], 1)
	rightCount.append(freCount[arr[i]])
rightCount = rightCount[::-1]
for i in range(n):
	update(ft, rightCount[i], -1)
	ans += query(ft, leftCount[i] - 1) if leftCount[i] > 1 else 0
print(ans)


from itertools import combinations, permutations
from collections import defaultdict
import math
import sys
import os

def zeror():
	return 0
prefix_sums = []
ftree = []

class FenwickTree(object):

	def __init__(self, n):
		self.tree = [0] * (n + 1)

	def update(self, i, v):
		i += 1
		while i < len(self.tree):
			self.tree[i] += v
			i = i + (~i + 1 & i)

	def query(self, l, r):
		lt = 0
		i = l
		while i != 0:
			lt += self.tree[i]
			i = i - (~i + 1 & i)
		rt = 0
		i = r + 1
		while i != 0:
			rt += self.tree[i]
			i -= ~i + 1 & i
		return rt - lt

def solution(n, a):
	onetoi = []
	seen1i = defaultdict(int)
	for i in range(n):
		seen1i[a[i]] += 1
		onetoi.append(seen1i[a[i]])
	jton = []
	seenjn = defaultdict(int)
	for j in range(n - 1, -1, -1):
		seenjn[a[j]] += 1
		jton.append(seenjn[a[j]])
	jton = jton[::-1]
	fw = FenwickTree(1000000)
	for v in jton:
		fw.update(v, 1)
	t = 0
	for i in range(n):
		fw.update(jton[i], -1)
		t += fw.query(0, onetoi[i] - 1)
	return t

def main():
	n = int(input())
	arr = list(map(int, input().strip().split()))
	print(solution(n, arr))

def __starting_point():
	main()
__starting_point()


bit = [0 for i in range(int(2000000.0 + 1))]
n = int(input())

def add(ind, x):
	ind += 1
	while ind <= n:
		bit[ind] += x
		ind += ind & -ind

def getsum(ind):
	ans = 0
	ind += 1
	while ind > 0:
		ans += bit[ind]
		ind -= ind & -ind
	return ans
a = list(map(int, input().split()))
b = [i for i in a]
b.sort()
d = {}
for i in range(n):
	d[b[i]] = i
b = []
for i in a:
	b.append(d[i])
a1 = [0 for i in range(n)]
f1 = []
for i in b:
	a1[i] += 1
	f1.append(a1[i])
f2 = []
a1 = [0 for i in range(n)]
b.reverse()
for i in b:
	a1[i] += 1
	f2.append(a1[i])
b.reverse()
f2.reverse()
ans = 0
for i in range(n - 1, -1, -1):
	ans += getsum(f1[i] - 1)
	add(f2[i], 1)
print(ans)


class SegTree:

	def __init__(self, arr=None, length=None):
		if arr is not None:
			self.n = len(arr)
			self.t = [0 for _ in range(2 * self.n)]
			self.construct(arr)
		else:
			self.n = length
			self.t = [0 for _ in range(2 * self.n)]

	def construct(self, a):
		self.t[self.n:] = arr
		for i in reversed(range(0, self.n - 1)):
			self.t[i] = self.t[i * 2] + self.t[i * 2 + 1]

	def modify(self, p, val):
		p += self.n
		self.t[p] = val
		while p > 1:
			self.t[p // 2] = self.t[p] + self.t[p ^ 1]
			p //= 2

	def query(self, l, r):
		res = 0
		l += self.n
		r += self.n
		while l < r:
			if l & 1:
				res += self.t[l]
				l += 1
			if r & 1:
				r -= 1
				res += self.t[r]
			l //= 2
			r //= 2
		return res
n = int(input())
l = [int(x) for x in input().split()]
front_fs = []
ct = {}
for v in l:
	if v not in ct:
		ct[v] = 0
	ct[v] += 1
	front_fs.append(ct[v])
back_fs = []
ct = {}
for v in reversed(l):
	if v not in ct:
		ct[v] = 0
	ct[v] += 1
	back_fs.append(ct[v])
back_fs = list(reversed(back_fs))
tot = 0
done = SegTree(length=n)
for (fval_f, fval_b) in zip(front_fs, back_fs):
	tot += done.query(fval_b + 1, n)
	if fval_f == n:
		break
	done.modify(fval_f, done.query(fval_f, fval_f + 1) + 1)
print(tot)


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

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

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

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

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

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
n = int(input())
b = list(map(int, input().split()))
d = dict()
pre = []
j = 0
while j <= n - 1:
	if b[j] in d.keys():
		d[b[j]] += 1
	else:
		d[b[j]] = 1
	pre.append(d[b[j]])
	j += 1
suff = []
d = dict()
j = n - 1
while j >= 0:
	if b[j] in d.keys():
		d[b[j]] += 1
	else:
		d[b[j]] = 1
	suff.append(d[b[j]])
	j += -1
suff.reverse()

def update(bit, index, val):
	l = len(bit)
	while index < l:
		bit[index] += val
		index += index & -1 * index

def getsum(bit, index):
	ans = 0
	while index > 0:
		ans += bit[index]
		index -= index & -1 * index
	return ans
l = len(pre)
bit = [0] * (max(suff) + 1)
res = 0
j = l - 1
while j >= 0:
	res += getsum(bit, pre[j] - 1)
	update(bit, suff[j], 1)
	j += -1
print(res)


import sys
import io
import math
import collections
import decimal
import itertools
import bisect
import array

def input():
	return sys.stdin.readline()[:-1]

def add(i, x):
	i += N1
	Dat[i] += x
	i //= 2
	while i > 0:
		Dat[i] = Dat[i * 2] + Dat[i * 2 + 1]
		i //= 2

def query(l, r):
	v = 0
	l += N1
	r += N1
	while l < r:
		if l & 1:
			v += Dat[l]
			l += 1
		if r & 1:
			v += Dat[r - 1]
			r -= 1
		l //= 2
		r //= 2
	return v

def debug():
	depth = 0
	print('Segment Tree -----------------')
	while 2 ** depth < 2 * N1:
		print(*Dat[2 ** depth:2 ** (depth + 1)])
		depth += 1
N = int(input())
A = list(map(int, input().split()))
N1 = 2 ** (N - 1).bit_length()
Dat = [0] * (2 * N1)
D = {a: i for (i, a) in enumerate(sorted(set(A)))}
B = [D[a] for a in A]
Count1 = array.array('i', [0] * N)
T1 = [list() for _ in range(N)]
for i in range(N):
	v = Count1[B[i]]
	T1[v].append(i)
	Count1[B[i]] += 1
Count2 = array.array('i', [0] * N)
T2 = [list() for _ in range(N)]
for i in reversed(range(N)):
	v = Count2[B[i]]
	T2[v].append(i)
	Count2[B[i]] += 1
ans = 0
for i in range(1, N):
	for k in T2[i - 1]:
		add(k, 1)
	for l in T1[i]:
		n = query(l + 1, N)
		ans += n
print(ans)


BIT = [0] * 10 ** 7

def query_BIT(i):
	res = 0
	while i > 0:
		res += BIT[i]
		i -= i & -i
	return res

def add_to_BIT(n, p):
	while p <= n:
		BIT[p] += 1
		p += p & -p

def main():
	n = int(input())
	arr = [int(i) for i in input().split(' ')]
	pre = [0] * n
	suf = [0] * n
	d_map = {}
	for i in range(n):
		val = arr[i]
		if val not in d_map:
			d_map[val] = 1
		else:
			d_map[val] += 1
		pre[i] = d_map[val]
	d_map.clear()
	for i in range(n - 1, -1, -1):
		val = arr[i]
		if val not in d_map:
			d_map[val] = 1
		else:
			d_map[val] += 1
		suf[i] = d_map[val]
	ans = 0
	for i in range(n - 1, -1, -1):
		ans += query_BIT(pre[i] - 1)
		add_to_BIT(n, suf[i])
	print(ans)
main()


import math, sys, bisect, heapq, os
from collections import defaultdict, Counter, deque
from itertools import groupby, accumulate
from functools import lru_cache
pr = lambda x: x

def input():
	return sys.stdin.readline().rstrip('\r\n')
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])

def solve():
	(n,) = aj()
	B = aj()
	if n <= 2:
		print(0)
	elif len(set(B)) == n:
		print(0)
	else:

		def BIT(n):
			Tree = [0] * (n + 1)
			arr = [0] * (n + 1)
			return (Tree, arr)

		def update(i, dif):
			arr[i] += dif
			i += 1
			while i <= n:
				Tree[i] += dif
				i += i & -i

		def getvalue(i):
			s = 0
			i += 1
			while i > 0:
				s += Tree[i]
				i -= i & -i
			return s

		def query(l, r):
			if l == 0:
				return getvalue(r)
			else:
				return getvalue(r) - getvalue(l - 1)
		ans = 0
		C = Counter()
		A = [0] * n
		for i in range(n - 1, -1, -1):
			A[i] = C[B[i]] + 1
			C[B[i]] += 1
		(Tree, arr) = BIT(n + 1)
		for i in range(1, n):
			update(A[i], 1)
		C = Counter()
		C[B[0]] += 1
		for i in range(1, n - 1):
			C[B[i]] += 1
			v = C[B[i]]
			update(A[i], -1)
			count = query(0, v - 1)
			ans += count
		print(ans)
try:
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
	from aj import *
except:
	pass
solve()


def merge(a, x, y, u, v):
	i = 0
	b = a[x:v + 1]
	j = u
	for k in range(x, y + 1):
		while j <= v and a[j] < a[k]:
			b[i] = a[j]
			j += 1
			i += 1
		b[i] = a[k]
		i += 1
	while j <= u:
		b[i] = a[j]
		i += 1
		j += 1
	return b

def cal(l, r, x, y):
	if x == y:
		return 0
	mid = (x + y) // 2
	res = cal(l, r, x, mid) + cal(l, r, mid + 1, y)
	j = mid + 1
	for i in range(x, mid + 1):
		while j <= y and r[j] < l[i]:
			j += 1
		res += j - mid - 1
	l[x:y + 1] = merge(l, x, mid, mid + 1, y)
	r[x:y + 1] = merge(r, x, mid, mid + 1, y)
	return res

def countOccurrencePairs(a):
	n = len(a)
	l = [0 for _ in range(n)]
	d = {}
	for i in range(n):
		if a[i] not in d:
			d[a[i]] = 0
		d[a[i]] += 1
		l[i] = d[a[i]]
	r = [0 for _ in range(n)]
	d = {}
	for i in range(n - 1, -1, -1):
		if a[i] not in d:
			d[a[i]] = 0
		d[a[i]] += 1
		r[i] = d[a[i]]
	return cal(l, r, 0, n - 1)
n = int(input())
a = list(map(int, input().split()))
print(countOccurrencePairs(a))


import sys
from collections import Counter

class BIT:

	def __init__(self, n):
		self.n = n
		self.tree = [0] * n

	def _F(self, i):
		return i & i + 1

	def _getSum(self, r):
		result = 0
		while r >= 0:
			result += self.tree[r]
			r = self._F(r) - 1
		return result

	def getSum(self, l, r):
		return self._getSum(r) - self._getSum(l - 1)

	def _H(self, i):
		return i | i + 1

	def add(self, i, value=1):
		while i < self.n:
			self.tree[i] += value
			i = self._H(i)
reader = (line.rstrip() for line in sys.stdin)
input = reader.__next__
n = int(input())
a = list(map(int, input().split()))
freq = BIT(n + 1)
f_left = [0] * n
f_right = [0] * n
ctr = Counter()
for (i, val) in enumerate(a):
	ctr[val] += 1
	f_left[i] = ctr[val]
for i in range(n):
	val = a[i]
	f_right[i] = ctr[val] - f_left[i] + 1
for f_r in f_right:
	freq.add(f_r, 1)
ans = 0
for (i, f_l) in enumerate(f_left):
	f_r = f_right[i]
	freq.add(f_r, -1)
	ans += freq.getSum(1, f_l - 1)
print(ans)


import collections
import time
import os
import sys
import bisect
import heapq
from typing import List

def solve(N, A):
	B = list(sorted(set(A)))
	vi = {v: i for (i, v) in enumerate(B)}
	A = [vi[v] for v in A]
	wc = collections.defaultdict(int)
	precount = [0 for _ in range(N)]
	for (i, v) in enumerate(A):
		wc[v] += 1
		precount[i] = wc[v]
	wc = collections.defaultdict(int)
	sufcount = []
	for v in reversed(A):
		wc[v] += 1
		sufcount.append(wc[v])
	sufcount = sufcount[::-1]
	bit = [0 for _ in range(N)]

	def add(index, val):
		while index < N:
			bit[index] += val
			index |= index + 1

	def query(index):
		s = 0
		while index >= 0:
			s += bit[index]
			index = (index & index + 1) - 1
		return s
	ans = 0
	for i in range(N - 2, -1, -1):
		v = precount[i]
		add(sufcount[i + 1], 1)
		ans += query(v - 1)
	return ans
N = int(input())
A = [int(x) for x in input().split()]
print(solve(N, A))


n = int(input())
a = list(map(int, input().split()))
fen = [0] * (n + 1)

def update(index, value):
	while index <= n:
		fen[index] += value
		index += index & -index

def get(p):
	ans = 0
	while p > 0:
		ans += fen[p]
		p -= p & -p
	return ans
l = [0] * n
r = [0] * n
cnt = [0] * (n + 1)
appearances = {}
for i in range(n - 1, -1, -1):
	if a[i] in appearances.keys():
		appearances[a[i]] += 1
	else:
		appearances[a[i]] = 1
	r[i] = appearances[a[i]]
	update(r[i], 1)
appearances = {}
res = 0
for i in range(n):
	if a[i] in appearances.keys():
		appearances[a[i]] += 1
	else:
		appearances[a[i]] = 1
	l[i] = appearances[a[i]]
	update(r[i], -1)
	res += get(l[i] - 1)
print(res)


import sys
input = sys.stdin.readline
n = int(input())
ar = list(map(int, input().split()))
li = []
dic = {}
for i in range(1, n + 1):
	if ar[-i] in dic:
		dic[ar[-i]] += 1
	else:
		dic[ar[-i]] = 1
	li.append(dic[ar[-i]])
br = [0] * (n + 1)
for i in range(n):
	br[li[i]] += 1
for idx in range(1, n + 1):
	idx2 = idx + (idx & -idx)
	if idx2 < n:
		br[idx2] += br[idx]
main = 0
front = []
dic = {}
for i in range(n):
	if ar[i] in dic:
		dic[ar[i]] += 1
	else:
		dic[ar[i]] = 1
	front.append(dic[ar[i]])
for i in range(n - 1):
	inp = li[n - i - 1]
	add = -1
	while inp < n + 1:
		br[inp] += add
		inp += inp & -inp
	if inp != 1:
		inp -= 1
		add = 1
		while inp < n + 1:
			br[inp] += add
			inp += inp & -inp
	ans = 0
	inp = front[i]
	if inp != 1:
		inp -= 1
		while inp:
			ans += br[inp]
			inp -= inp & -inp
		main += ans
print(main)


import os
import sys
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')

def inp():
	return sys.stdin.readline().rstrip()

def mpint():
	return map(int, inp().split(' '))

def itg():
	return int(inp())

class FenwickTree:

	def __init__(self, x=[]):
		self.bit = x
		for i in range(len(x)):
			j = i | i + 1
			if j < len(x):
				x[j] += x[i]

	def update(self, idx, x):
		while idx < len(self.bit):
			self.bit[idx] += x
			idx |= idx + 1

	def query(self, end):
		x = 0
		while end:
			x += self.bit[end - 1]
			end &= end - 1
		return x

	def findkth(self, k):
		idx = -1
		for d in reversed(range(len(self.bit).bit_length())):
			right_idx = idx + (1 << d)
			if right_idx < len(self.bit) and k >= self.bit[right_idx]:
				idx = right_idx
				k -= self.bit[idx]
		return idx + 1
from collections import Counter

def solve():
	n = itg()
	arr = tuple(mpint())
	(pre, suf) = (Counter(), Counter(arr))
	fi = [0] * n
	fj = [0] * n
	for (i, a) in enumerate(arr):
		pre[a] += 1
		fi[i] = pre[a]
		fj[i] = suf[a]
		suf[a] -= 1
	bit = FenwickTree([0] * (n + 1))
	ans = 0
	for i in reversed(range(n)):
		ans += bit.query(fi[i])
		bit.update(fj[i], 1)
	return ans

def main():
	print(solve())
DEBUG = 0
URL = 'https://codeforces.com/contest/459/problem/D'
if DEBUG == 1:
	import requests
	from ACgenerator.Y_Test_Case_Runner import TestCaseRunner
	runner = TestCaseRunner(main, URL)
	inp = runner.input_stream
	print = runner.output_stream
	runner.checking()
elif DEBUG == 2:
	main()
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
	main()


from sys import *

class SortedList:

	def __init__(self, iterable=None, _load=200):
		if iterable is None:
			iterable = []
		values = sorted(iterable)
		self._len = _len = len(values)
		self._load = _load
		self._lists = _lists = [values[i:i + _load] for i in range(0, _len, _load)]
		self._list_lens = [len(_list) for _list in _lists]
		self._mins = [_list[0] for _list in _lists]
		self._fen_tree = []
		self._rebuild = True

	def _fen_build(self):
		self._fen_tree[:] = self._list_lens
		_fen_tree = self._fen_tree
		for i in range(len(_fen_tree)):
			if i | i + 1 < len(_fen_tree):
				_fen_tree[i | i + 1] += _fen_tree[i]
		self._rebuild = False

	def _fen_update(self, index, value):
		if not self._rebuild:
			_fen_tree = self._fen_tree
			while index < len(_fen_tree):
				_fen_tree[index] += value
				index |= index + 1

	def _fen_query(self, end):
		if self._rebuild:
			self._fen_build()
		_fen_tree = self._fen_tree
		x = 0
		while end:
			x += _fen_tree[end - 1]
			end &= end - 1
		return x

	def _fen_findkth(self, k):
		_list_lens = self._list_lens
		if k < _list_lens[0]:
			return (0, k)
		if k >= self._len - _list_lens[-1]:
			return (len(_list_lens) - 1, k + _list_lens[-1] - self._len)
		if self._rebuild:
			self._fen_build()
		_fen_tree = self._fen_tree
		idx = -1
		for d in reversed(range(len(_fen_tree).bit_length())):
			right_idx = idx + (1 << d)
			if right_idx < len(_fen_tree) and k >= _fen_tree[right_idx]:
				idx = right_idx
				k -= _fen_tree[idx]
		return (idx + 1, k)

	def _delete(self, pos, idx):
		_lists = self._lists
		_mins = self._mins
		_list_lens = self._list_lens
		self._len -= 1
		self._fen_update(pos, -1)
		del _lists[pos][idx]
		_list_lens[pos] -= 1
		if _list_lens[pos]:
			_mins[pos] = _lists[pos][0]
		else:
			del _lists[pos]
			del _list_lens[pos]
			del _mins[pos]
			self._rebuild = True

	def _loc_left(self, value):
		if not self._len:
			return (0, 0)
		_lists = self._lists
		_mins = self._mins
		(lo, pos) = (-1, len(_lists) - 1)
		while lo + 1 < pos:
			mi = lo + pos >> 1
			if value <= _mins[mi]:
				pos = mi
			else:
				lo = mi
		if pos and value <= _lists[pos - 1][-1]:
			pos -= 1
		_list = _lists[pos]
		(lo, idx) = (-1, len(_list))
		while lo + 1 < idx:
			mi = lo + idx >> 1
			if value <= _list[mi]:
				idx = mi
			else:
				lo = mi
		return (pos, idx)

	def _loc_right(self, value):
		if not self._len:
			return (0, 0)
		_lists = self._lists
		_mins = self._mins
		(pos, hi) = (0, len(_lists))
		while pos + 1 < hi:
			mi = pos + hi >> 1
			if value < _mins[mi]:
				hi = mi
			else:
				pos = mi
		_list = _lists[pos]
		(lo, idx) = (-1, len(_list))
		while lo + 1 < idx:
			mi = lo + idx >> 1
			if value < _list[mi]:
				idx = mi
			else:
				lo = mi
		return (pos, idx)

	def add(self, value):
		_load = self._load
		_lists = self._lists
		_mins = self._mins
		_list_lens = self._list_lens
		self._len += 1
		if _lists:
			(pos, idx) = self._loc_right(value)
			self._fen_update(pos, 1)
			_list = _lists[pos]
			_list.insert(idx, value)
			_list_lens[pos] += 1
			_mins[pos] = _list[0]
			if _load + _load < len(_list):
				_lists.insert(pos + 1, _list[_load:])
				_list_lens.insert(pos + 1, len(_list) - _load)
				_mins.insert(pos + 1, _list[_load])
				_list_lens[pos] = _load
				del _list[_load:]
				self._rebuild = True
		else:
			_lists.append([value])
			_mins.append(value)
			_list_lens.append(1)
			self._rebuild = True

	def discard(self, value):
		_lists = self._lists
		if _lists:
			(pos, idx) = self._loc_right(value)
			if idx and _lists[pos][idx - 1] == value:
				self._delete(pos, idx - 1)

	def remove(self, value):
		_len = self._len
		self.discard(value)
		if _len == self._len:
			raise ValueError('{0!r} not in list'.format(value))

	def pop(self, index=-1):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		value = self._lists[pos][idx]
		self._delete(pos, idx)
		return value

	def bisect_left(self, value):
		(pos, idx) = self._loc_left(value)
		return self._fen_query(pos) + idx

	def bisect_right(self, value):
		(pos, idx) = self._loc_right(value)
		return self._fen_query(pos) + idx

	def count(self, value):
		return self.bisect_right(value) - self.bisect_left(value)

	def __len__(self):
		return self._len

	def __getitem__(self, index):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		return self._lists[pos][idx]

	def __delitem__(self, index):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		self._delete(pos, idx)

	def __contains__(self, value):
		_lists = self._lists
		if _lists:
			(pos, idx) = self._loc_left(value)
			return idx < len(_lists[pos]) and _lists[pos][idx] == value
		return False

	def __iter__(self):
		return (value for _list in self._lists for value in _list)

	def __reversed__(self):
		return (value for _list in reversed(self._lists) for value in reversed(_list))

	def __repr__(self):
		return 'SortedList({0})'.format(list(self))
n = int(stdin.readline())
a = list(map(int, stdin.readline().split()))
d = {}
x = 0
for i in range(n):
	if a[i] not in d:
		d[a[i]] = x
		x += 1
for i in range(n):
	a[i] = d[a[i]]
cnt = [0] * x
left = [0] * n
right = [0] * n
for i in range(n):
	cnt[a[i]] += 1
	left[i] = cnt[a[i]]
for i in range(x):
	cnt[i] = 0
for i in range(n - 1, -1, -1):
	cnt[a[i]] += 1
	right[i] = cnt[a[i]]
arr = SortedList(left)
ans = 0
for i in range(n - 1, 0, -1):
	arr.discard(left[i])
	pos = arr.bisect_right(right[i])
	ans += len(arr) - pos
stdout.write(str(ans) + '\n')


n = int(input())
l = [int(j) for j in input().split()]
d = dict()
pre = []
for i in range(n):
	if l[i] in d:
		d[l[i]] += 1
	else:
		d[l[i]] = 1
	pre.append(d[l[i]])
suf = [0 for i in range(n)]
d = dict()
for i in range(n - 1, -1, -1):
	if l[i] in d:
		d[l[i]] += 1
	else:
		d[l[i]] = 1
	suf[i] = d[l[i]]

def update(bit, index, val):
	n = len(bit)
	while index < n:
		bit[index] += val
		index += index & -1 * index

def getsum(bit, index):
	n = len(bit)
	ans = 0
	while index > 0:
		ans += bit[index]
		index -= index & -1 * index
	return ans
n = len(pre)
bit = [0] * (max(suf) + 1)
inv_ct = 0
for i in range(n - 1, -1, -1):
	inv_ct += getsum(bit, pre[i] - 1)
	update(bit, suf[i], 1)
print(inv_ct)


import sys
input = sys.stdin.readline
n = int(input())
t = list(map(int, input().split()))
d = dict()
j = 0
prefix = []
while j <= n - 1:
	if t[j] not in d:
		d[t[j]] = 1
	else:
		d[t[j]] += 1
	prefix.append(d[t[j]])
	j += 1
suff = []
d = dict()
j = n - 1
while j >= 0:
	if t[j] not in d:
		d[t[j]] = 1
	else:
		d[t[j]] += 1
	suff.append(d[t[j]])
	j -= 1
suff = suff[::-1]

def update(bit, index, val):
	p = len(bit)
	while index < p:
		bit[index] += val
		index += index & -index

def getsum(bit, index):
	ans = 0
	while index > 0:
		ans += bit[index]
		index -= index & -index
	return ans
l = len(prefix)
bit = [0] * (len(suff) + 1)
res = 0
j = l - 1
while j >= 0:
	res += getsum(bit, prefix[j] - 1)
	update(bit, suff[j], 1)
	j += -1
print(res)