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 java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.io.FilterInputStream;
import java.io.BufferedInputStream;
import java.util.HashMap;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author Jenish
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        ScanReader in = new ScanReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        DPashmakAndParmidasProblem solver = new DPashmakAndParmidasProblem();
        solver.solve(1, in, out);
        out.close();
    }

    static class DPashmakAndParmidasProblem {
        public void solve(int testNumber, ScanReader in, PrintWriter out) {
            int n = in.scanInt();
            long arr[] = new long[n];
            HashMap<Long, Integer> hm = new HashMap<>();
            int pre[] = new int[n];
            for (int i = 0; i < n; i++) {
                arr[i] = in.scanLong();
                if (hm.containsKey(arr[i])) {
                    hm.put(arr[i], hm.get(arr[i]) + 1);
                } else {
                    hm.put(arr[i], 1);
                }
                pre[i] = hm.get(arr[i]);
            }


            hm = new HashMap<>();
            int suf[] = new int[n];
            for (int i = n - 1; i >= 0; i--) {
                if (hm.containsKey(arr[i])) {
                    hm.put(arr[i], hm.get(arr[i]) + 1);
                } else {
                    hm.put(arr[i], 1);
                }
                suf[i] = hm.get(arr[i]);
            }


            long ans = 0;

            MergeSortTree mergeSortTree = new MergeSortTree(suf, n);
            for (int i = 0; i < n - 1; i++) {
                int l = i + 1;
                int r = n - 1;
                ans += mergeSortTree.smallerK(l, r, pre[i] - 1);
            }

            out.println(ans);

        }

    }

    static class MergeSortTree {
        int[][] tree;
        int[] arr;
        int n;

        public MergeSortTree(int[] arr, int n) {
            this.arr = arr;
            this.n = n;
            tree = new int[(4 * n) + 5][];
            build_tree(1, 0, n - 1);
        }

        public int smallerK(int l, int r, int k) {
            return querytree(1, 0, n - 1, l, r, k);
        }

        private void build_tree(int node, int l, int r) {
            if (l == r) {
                tree[node] = new int[]{arr[l]};
                return;
            }
            int mid = (l + r) / 2;
            build_tree((2 * node), l, mid);
            build_tree((2 * node) + 1, mid + 1, r);
            tree[node] = merge(tree[2 * node], tree[2 * node + 1]);
        }

        private int[] merge(int[] tree1, int[] tree2) {
            int[] tree = new int[tree1.length + tree2.length];
            int i = 0;
            int j = 0;
            int k = 0;
            while (i < tree1.length && j < tree2.length) {
                if (tree1[i] > tree2[j]) tree[k++] = tree2[j++];
                else tree[k++] = tree1[i++];
            }
            while (i < tree1.length) tree[k++] = tree1[i++];
            while (j < tree2.length) tree[k++] = tree2[j++];
            return tree;
        }

        private int querytree(int node, int start, int end, int l, int r, int k) {
            if (r < start || end < l) return 0;
            if (l <= start && end <= r) {
                int low = 0;
                int high = tree[node].length - 1;
                while (low <= high) {
                    int mid = (low + high) / 2;
                    if (tree[node][mid] > k) {
                        high = mid - 1;
                    } else {
                        low = mid + 1;
                    }
                }
                return low;
            }
            int mid = (start + end) / 2;
            return querytree(2 * node, start, mid, l, r, k) + querytree(2 * node + 1, mid + 1, end, l, r, k);
        }

    }

    static class ScanReader {
        private byte[] buf = new byte[4 * 1024];
        private int INDEX;
        private BufferedInputStream in;
        private int TOTAL;

        public ScanReader(InputStream inputStream) {
            in = new BufferedInputStream(inputStream);
        }

        private int scan() {
            if (INDEX >= TOTAL) {
                INDEX = 0;
                try {
                    TOTAL = in.read(buf);
                } catch (Exception e) {
                    e.printStackTrace();
                }
                if (TOTAL <= 0) return -1;
            }
            return buf[INDEX++];
        }

        public int scanInt() {
            int I = 0;
            int n = scan();
            while (isWhiteSpace(n)) n = scan();
            int neg = 1;
            if (n == '-') {
                neg = -1;
                n = scan();
            }
            while (!isWhiteSpace(n)) {
                if (n >= '0' && n <= '9') {
                    I *= 10;
                    I += n - '0';
                    n = scan();
                }
            }
            return neg * I;
        }

        private boolean isWhiteSpace(int n) {
            if (n == ' ' || n == '\n' || n == '\r' || n == '\t' || n == -1) return true;
            else return false;
        }

        public long scanLong() {
            long I = 0;
            int n = scan();
            while (isWhiteSpace(n)) n = scan();
            int neg = 1;
            if (n == '-') {
                neg = -1;
                n = scan();
            }
            while (!isWhiteSpace(n)) {
                if (n >= '0' && n <= '9') {
                    I *= 10;
                    I += n - '0';
                    n = scan();
                }
            }
            return neg * I;
        }

    }
}

