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 a1, a2, ..., an. Let's denote f(l, r, x) the number of indices k such that: l ≤ k ≤ r and ak = x. His task is to calculate the number of pairs of indicies i, j (1 ≤ i < j ≤ n) such that f(1, i, ai) > f(j, n, aj).

Help Pashmak with the test.

Input

The first line of the input contains an integer n (1 ≤ n ≤ 106). The second line contains n space-separated integers a1, a2, ..., an (1 ≤ ai ≤ 109).

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
class SegTree:
    def __init__(self, arr = None, length = None):
        """
        Creates a segment tree. If arr (a list) is given, length is ignored,
        and we build a segment tree with underlying array arr. If no list is
        given, length (an int) must be given, and we build a segment tree with
        underlying all-zero array of that length.
        """
        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):
        """
        Constructs the segment tree from given array (assumed to be of the
        right length).
        """
        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):
        """
        Sets the value at index p to 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):
        """
        Gets the sum of all values in the range [l, r) in the underlying array.
        """
        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(fval_f, fval_b, tot)
print(tot)
