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
import sun.reflect.generics.tree.Tree;

import java.io.*;
import java.math.*;
import java.util.*;
import java.lang.*;

public class Main implements Runnable {
    static class InputReader {
        private InputStream stream;
        private byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;
        private SpaceCharFilter filter;
        private BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        public InputReader(InputStream stream) {
            this.stream = stream;
        }

        public int read() {
            if (numChars == -1)
                throw new InputMismatchException();

            if (curChar >= numChars) {
                curChar = 0;
                try {
                    numChars = stream.read(buf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }

                if (numChars <= 0)
                    return -1;
            }
            return buf[curChar++];
        }

        public String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }

        public int nextInt() {
            int c = read();

            while (isSpaceChar(c))
                c = read();

            int sgn = 1;

            if (c == '-') {
                sgn = -1;
                c = read();
            }

            int res = 0;
            do {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = read();
            }
            while (!isSpaceChar(c));

            return res * sgn;
        }

        public long nextLong() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            long res = 0;

            do {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = read();
            }
            while (!isSpaceChar(c));
            return res * sgn;
        }

        public double nextDouble() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            double res = 0;
            while (!isSpaceChar(c) && c != '.') {
                if (c == 'e' || c == 'E')
                    return res * Math.pow(10, nextInt());
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = read();
            }
            if (c == '.') {
                c = read();
                double m = 1;
                while (!isSpaceChar(c)) {
                    if (c == 'e' || c == 'E')
                        return res * Math.pow(10, nextInt());
                    if (c < '0' || c > '9')
                        throw new InputMismatchException();
                    m /= 10;
                    res += (c - '0') * m;
                    c = read();
                }
            }
            return res * sgn;
        }

        public String readString() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            StringBuilder res = new StringBuilder();
            do {
                res.appendCodePoint(c);
                c = read();
            }
            while (!isSpaceChar(c));

            return res.toString();
        }

        public boolean isSpaceChar(int c) {
            if (filter != null)
                return filter.isSpaceChar(c);
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

        public String next() {
            return readString();
        }

        public interface SpaceCharFilter {
            public boolean isSpaceChar(int ch);
        }
    }

    public static void main(String args[]) throws Exception {
        new Thread(null, new Main(), "Main", 1 << 26).start();
    }

    static long gcd(long a, long b) {
        if (b == 0) return a;
        return gcd(b, a % b);
    }

    static int gcd(int a, int b) {
        if (b == 0) return a;
        return gcd(b, a % b);
    }

    static long modPow(long a, long p, long m) {
        if (a == 1) return 1;
        long ans = 1;
        while (p > 0) {
            if (p % 2 == 1) ans = (ans * a) % m;
            a = (a * a) % m;
            p >>= 1;
        }
        return ans;
    }

    static long modInv(long a, long m) {
        return modPow(a, m - 2, m);
    }

    static long sol_x, sol_y, gcd_a_b;

    static void extendedEuclid(long a, long b) {
        if (b == 0) {
            gcd_a_b = a;
            sol_x = 1;
            sol_y = 0;
        } else {
            extendedEuclid(b, a % b);
            long temp = sol_x;
            sol_x = sol_y;
            sol_y = temp - (a / b) * sol_y;
        }
    }

    long modInverse(long a, long prime)
    {
        a = a % prime;
        for (int x=1; x<prime; x++)
            if ((a*x) % prime == 1)
                return x;

        return -1;
    }

    static class Bhavansort {
        Random random;

        Bhavansort(int a[]) {
            randomArray(a);
            sort(a);
        }

        Bhavansort(long a[]) {
            randomArray(a);
            sort(a);
        }

        static int[] sort(int a[]) {
            Arrays.sort(a);
            return a;
        }

        static long[] sort(long a[]) {
            Arrays.sort(a);
            return a;
        }

        void randomArray(long a[]) {
            int n = a.length;
            for (int i = 0; i < n; i++) {
                int p = random.nextInt(n) % n;
                long tm = a[i];
                a[i] = a[p];
                a[p] = tm;
            }
        }

        void randomArray(int a[]) {
            int n = a.length;
            for (int i = 0; i < n; i++) {
                int p = random.nextInt(n) % n;
                int tm = a[i];
                a[i] = a[p];
                a[p] = tm;
            }
        }
    }


    public void run() {
        InputReader sc = new InputReader(System.in);
        //Scanner sc=new Scanner(System.in);
        // Random rn=new Random();
        PrintWriter out = new PrintWriter(System.out);


        int n=sc.nextInt();
        int a[][]=new int[n][2];
        for (int i = 0; i <n ; i++) {
            a[i][0]=sc.nextInt();
            a[i][1]=i;
        }
        HashMap<Integer,Integer> map=new HashMap<>();
        int pre[]=new int[n];
        int suf[]=new int[n];
        for (int i = 0; i <n ; i++) {
            if(map.containsKey(a[i][0])){
                map.put(a[i][0],map.get(a[i][0])+1);
            }
            else{
                map.put(a[i][0],1);
            }
            pre[i]=map.get(a[i][0]);
        }
        map=new HashMap<>();
        for (int i = n-1; i >=0 ; i--) {
            if(map.containsKey(a[i][0])){
                map.put(a[i][0],map.get(a[i][0])+1);
            }
            else{
                map.put(a[i][0],1);
            }
            suf[i]=map.get(a[i][0]);
        }

        FenwickTree ft=new FenwickTree(n);
        ft.update(suf[n-1],1);
        long ans=0;
        for (int i = n-2; i >=0 ; i--) {
            ans+=ft.query(pre[i]-1);
            ft.update(suf[i],1);
        }
        out.println(ans);
        out.close();
    }

    class FenwickTree
    {
        int[] ft;

        FenwickTree(int n) { ft = new int[n + 1]; }

        void update(int idx, int val)
        {
            while(idx < ft.length)
            {
                ft[idx] += val;
                idx += idx & -idx;
            }
        }

        int query(int idx)
        {
            int s = 0;
            while(idx > 0)
            {
                s += ft[idx];
                idx ^= idx & -idx;
            }
            return s;
        }
    }

    class Node{
        int val,c;

        public Node(int val, int c) {
            this.val = val;
            this.c = c;
        }
    }

    class ST{
        SegNode tree[];
        public ST(int n){
            tree=new SegNode[2*n];
        }
        SegNode opration(SegNode o1,SegNode o2){
            return new  SegNode(o1.val+o2.val);
        }
        void build(int cur,int l,int r,int a[]){
            if(l==r){
                tree[cur].val=a[l];
                return;
            }
            int mid=(l+r)>>1;
            build(2*cur+1,l,mid,a);
            build(cur*2+2,mid+1,r,a);
            tree[cur]=opration(tree[(cur<<1)+1],tree[(cur<<1)+2]);
        }
        void update(int cur,int l,int r,int changeIndex,int changeValue){
            if(l==r){
                tree[cur].val+=changeValue;
                return;
            }
            int mid=(l+r)>>1;
            if(mid>=changeIndex) {
                update(2 * cur + 1, l, mid, changeIndex,changeValue);
            }
            else {
                update(2 * mid + 2, mid + 1, r, changeIndex,changeValue);
            }
            tree[cur]=opration(tree[(cur<<1)+1],tree[(cur<<1)+2]);
        }

        SegNode query(int cur,int l,int r,int qstart,int qend){
            if(qstart>=l && r<=qend){
                return tree[cur];
            }
            int mid=(l+r)>>1;
            SegNode default1=null,default2=null;
            default1=query(2*cur+1,l,mid,qstart,qend);
            default2=query(2*cur+1,mid+1,r,qstart,qend);
            return opration(default1,default2);
        }

        class SegNode{
            int val;

            public SegNode(int val) {
                this.val = val;
            }
        }
    }

}
