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.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.InputMismatchException;
import java.util.Map;


/**
 * 459D
 *
 * @author hemenghai
 * @date 2019/1/15 13:39
 */
public class Main {
    private static int n;

    private static int ai, bi, ci, di;
    private static int[] aix, bix, cix, dix;
    private static int[][] aixx, bixx, cixx, dixx;
    private static long al, bl, cl, dl;
    private static long[] alx, blx, clx, dlx;
    private static char ac, bc, cc, dc;
    private static char[] acx, bcx, ccx, dcx;
    private static double ad, bd, cd, dd;
    private static String as, bs, cs, ds;
    private static String[] asx, bsx, csx, dsx;

    public static void main(String[] args) {
        InputReader in = new InputReader(System.in);
        n = in.nextInt();

        aix = new int[n];
        for (int i = 0; i < n; i++) {
            aix[i] = in.nextInt();
        }

        int[] left = new int[n];
        Map<Integer, Integer> leftMap = new HashMap<>(n);
        int cnt;
        for (int i = 0; i < n; i++) {
            cnt = leftMap.getOrDefault(aix[i], 0);
            left[i] = cnt + 1;
            leftMap.put(aix[i], cnt + 1);
        }

        int[] right = new int[n];
        Map<Integer, Integer> rightMap = new HashMap<>(n);
        for (int i = n - 1; i > 0; i--) {
            cnt = rightMap.getOrDefault(aix[i], 0);
            right[i] = cnt + 1;
            rightMap.put(aix[i], cnt + 1);
        }

        bix = new int[n+1];
        long ans = 0;
        for (int i = 0; i < n; i++) {
            // 统计比当前right大的left有多少个
            ans += sum(n) - sum(right[i]);
            // 插入当前left
            add(left[i]);
        }
        System.out.println(ans);
    }

    private static int goLeft(int index) {
        return index - (index & -index);
    }

    private static int goRight(int index) {
        return index + (index & -index);
    }

    /**
     * 插入，复杂度为O(log2(n))
     */
    private static void add(int num) {
        for (int i = num; i <= n; i += i & (-i)) {
            bix[i]++;
        }
    }

    /**
     * 计算，复杂度为O(log2(n))
     */
    private static int sum(int num) {
        int ret = 0;
        for (int i = num; i > 0; i -= i & (-i)) {
            ret += bix[i];
        }
        return ret;
    }

    static class InputReader {

        private InputStream stream;
        private byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;
        private SpaceCharFilter filter;

        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() {
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            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 {
            boolean isSpaceChar(int ch);
        }
    }
}
