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

Difficulty: interview

Starter code:

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

def __starting_point():
    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(fl, fr)
    print(solve(fl, fr, 0, n - 1))
#     print(fl, fr)

__starting_point()

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
    res[k:] = l[i:] + r[j:]

    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

def __starting_point():
    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(fl, fr)
    print(solve(fl, fr, 0, n - 1))
#     print(fl, fr)

__starting_point()

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

    #print(onetoi)
    #print(seen1i)

    jton = []
    seenjn = defaultdict(int)
    for j in range(n - 1, -1, -1):
        seenjn[a[j]] += 1
        jton.append(seenjn[a[j]])

    #print(jton)
    #print(seenjn)

    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)
        #print(t)

    return t



def main():


    """a=[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16]
    ft = FenwickTree(len(a)*3)
    for i,v in enumerate(a):
        ft.update(i,v)
    print(ft.tree)
    print(ft.query(0,10))
    return"""

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


def __starting_point():
    main()


"""

7
1 2 1 1 2 2 1


"""
__starting_point()

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
# taking inputs

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
    #print(Map[A[index]])
    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)
    #print(ans)
stdout.write("%d"%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
    #print(Map[A[index]])
    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)
    #print(ans)
stdout.write("%d"%ans)
    











INF = 10 ** 10
# merge two sorted lists l and r
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

    res[k:] = l[i:] + r[j:]
    return res

def solve(fl, fr, l, r):
    if l == r:
        return 0
    
    mid = (l + r) // 2
    # after calling solve(l, mid) and (mid + 1, r), fl and fr are sorted on these ranges
    res = solve(fl, fr, l, mid) + solve(fl, fr, mid + 1, r)

    # perform 2-pointers on 2 sorted lists
    i, j = l, mid + 1
    while i <= mid:
        while j <= r and fr[j] < fl[i]:
            j += 1
        res += j - mid - 1
        i += 1
        
    # merge 2 sorted lists
    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

def __starting_point():
    n = int(input())
    a = list(map(int, input().split()))

    fl, cnt = [], {}
    for x in a:
        cnt[x] = cnt.get(x, 0) + 1
        # fl[i] = f(0, i, a[i])
        fl.append(cnt[x])

    fr, cnt = [], {}
    for x in a[::-1]:
        cnt[x] = cnt.get(x, 0) + 1
        # fr[i] = f(i, n - 1, a[i])
        fr.append(cnt[x])
    fr = fr[::-1]

    print(solve(fl, fr, 0, n - 1))

__starting_point()

# -*- coding:utf-8 -*-

"""

created by shuangquan.huang at 1/7/20

"""

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

# 459D
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):
        '''
        sum on interval [0, r]
        '''
        result = 0
        while r >= 0:
            result += self.tree[r]
            r = self._F(r) - 1
        return result
    
    def getSum(self, l, r):
        '''
        sum on interval [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)

# inf = open('input.txt', 'r')
# reader = (line.rstrip() for line in inf)
reader = (line.rstrip() for line in sys.stdin)
input = reader.__next__

n = int(input())
a = list(map(int, input().split()))
    
# inf.close()

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)


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


from collections import defaultdict
total = 0
def update(ft,pos,val):
    nonlocal 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)

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
# arr = [3, 6, 2, 4, 1, 7]
n = len(pre)
# print(pre, suf)
bit = [0]*(max(suf)+1)
inv_ct = 0
for i in range(n-1, -1, -1):
	# index = pre[i]
	inv_ct += getsum(bit, pre[i]-1)
	update(bit, suf[i], 1)
	# print(inv_ct, bit)
print(inv_ct)



# print(pre, suf)
# for i in range(n):
	# val = pre[i]


INF = 10 ** 10
# merge two sorted lists l and r
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

    res[k:] = l[i:] + r[j:]
    return res

def solve(fl, fr, l, r):
    if l == r:
        return 0
    
    mid = (l + r) // 2
    # after calling solve(l, mid) and (mid + 1, r), fl and fr are sorted on these ranges
    res = solve(fl, fr, l, mid) + solve(fl, fr, mid + 1, r)

    # perform 2-pointers on 2 sorted lists
    i, j = l, mid + 1
    while i <= mid:
        while j <= r and fr[j] < fl[i]:
            j += 1
        res += j - mid - 1
        i += 1
        
    # merge 2 sorted lists
    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

def __starting_point():
    n = int(input())
    a = list(map(int, input().split()))

    fl, cnt = [], {}
    for x in a:
        cnt[x] = cnt.get(x, 0) + 1
        # fl[i] = f(0, i, a[i])
        fl.append(cnt[x])

    fr, cnt = [], {}
    for x in a[::-1]:
        cnt[x] = cnt.get(x, 0) + 1
        # fr[i] = f(i, n - 1, a[i])
        fr.append(cnt[x])
    fr = fr[::-1]

    print(solve(fl, fr, 0, n - 1))

__starting_point()

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)

n=int(input())
def getsum(BITTree,i): 
    s = 0 #initialize result 
  
    # index in BITree[] is 1 more than the index in arr[] 
    i = i+1
  
    # Traverse ancestors of BITree[index] 
    while i > 0: 
  
        # Add current element of BITree to sum 
        s += BITTree[i] 
  
        # Move index to parent node in getSum View 
        i -= i & (-i) 
    return s 
  
# Updates a node in Binary Index Tree (BITree) at given index 
# in BITree. The given value 'val' is added to BITree[i] and 
# all of its ancestors in tree. 
def updatebit(BITTree , n , i ,v): 
  
    # index in BITree[] is 1 more than the index in arr[] 
    i += 1
  
    # Traverse all ancestors and add 'val' 
    while i <= n: 
  
        # Add 'val' to current node of BI Tree 
        BITTree[i] += v 
  
        # Update index to that of parent in update View 
        i += i & (-i) 
a=list(map(int,input().split()))
# print(*a)
pre=dict()
pos=dict()
for i in range(n):
    if(pre.get(a[i],None)==None):
        pre[a[i]]=0
    # if(pos.get(a[n-1-i],None)==None):
    #     pos[a[n-1-i]]=0 
    pre[a[i]]+=1 
    # pos[a[n-1-i]]+=1 
ans=0
BIT=[0]*(n+1)
for i in range(n-1,0,-1):
    # print(i)
    pre[a[i]]-=1 
    if(pos.get(a[i],None)==None):
        pos[a[i]]=0
    pos[a[i]]+=1 
    # print(pre)
    # print(pos)
    updatebit(BIT,n,pos[a[i]],1)
    # for j in range(7):
    #     print(getsum(BIT,j),end=' ')
    # print()
    #     print(getsum(BIT,j),end=' ')
    # print()
    # if pos[a[i]]>1:
    #     updatebit(BIT,n,pos[a[i]]-1,-1)
    # for j in range(7):
    temp=getsum(BIT,pre[a[i-1]]-1)
    ans+=temp
    # print(temp,pre[a[i-1]]-1,a[i-1],i)
print(ans)


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


#!/usr/bin/env python
# -*- coding: utf-8 -*-
#
#  sem título.py
#  
#  Copyright 2020 Alencar <Alencar@ALENCAR-PC>
#  
#  This program is free software; you can redistribute it and/or modify
#  it under the terms of the GNU General Public License as published by
#  the Free Software Foundation; either version 2 of the License, or
#  (at your option) any later version.
#  
#  This program is distributed in the hope that it will be useful,
#  but WITHOUT ANY WARRANTY; without even the implied warranty of
#  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
#  GNU General Public License for more details.
#  
#  You should have received a copy of the GNU General Public License
#  along with this program; if not, write to the Free Software
#  Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,
#  MA 02110-1301, USA.
#  
#  



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)



#!/usr/bin/env python3

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