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.*;
import java.util.*;

public class Main {
    private boolean eof;
    private BufferedReader br;
    private StringTokenizer st;
    private static PrintWriter out;

    public static void main(String[] args) throws IOException {
        new Main().run();
    }

    private String nextToken() {
        while (st == null || !st.hasMoreTokens()) {
            try {
                st = new StringTokenizer(br.readLine());
            } catch (Exception e) {
                eof = true;
                return "-1";
            }
        }
        return st.nextToken();
    }

    private int nextInt() {
        return Integer.parseInt(nextToken());
    }

    private long nextLong() {
        return Long.parseLong(nextToken());
    }

    private double nextDouble() {
        return Double.parseDouble(nextToken());
    }

    private String nextLine() throws IOException {
        return br.readLine();
    }


    private void run() throws IOException {
        InputStream input = System.in;
        PrintStream output = System.out;
        try {
            File f = new File("a.in");
            if (f.exists() && f.canRead()) {
                input = new FileInputStream(f);
                output = new PrintStream("a.out");
            }
        } catch (Throwable ignored) {
        }
        br = new BufferedReader(new InputStreamReader(input));
        out = new PrintWriter(new PrintWriter(output));
        solve();
        br.close();
        out.close();
    }

    private void solve() {
        int n = nextInt();

        HashMap<Integer, Integer> cnt = new HashMap<>();
        ArrayList<Integer> input = new ArrayList<>();
        ArrayList<Integer> fl = new ArrayList<>();
        ArrayList<Integer> fr = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            int x = nextInt();
            input.add(x);
            cnt.put(x, cnt.getOrDefault(x, 0) + 1);
            fl.add(cnt.get(x));
        }

        cnt.clear();
        for (int i = n - 1; i >= 0; i--) {
            cnt.put(input.get(i), cnt.getOrDefault(input.get(i), 0) + 1);
            fr.add(cnt.get(input.get(i)));
        }
        Collections.reverse(fr);

//        for (int c : fl) out.print(c + " ");
//        out.println();
//        for (int c : fr) out.print(c + " ");
//        out.println();

        Node root = null;
        for (int i = 1; i < n; i++) {
            root = insert(root, new Node(fr.get(i)));
        }

//        out.println(getKeysString(root));

        long ans = 0;
        for (int i = 1; i < n; i++) {
            Pair<Node, Integer> p = getCnt(root, fl.get(i - 1));
            root = p.first;
            ans += (long) p.second;
            root = remove(root, fr.get(i));
        }

        out.print(ans);
    }


    private static Random rnd = new Random();

    //Дерево поиска по ключу, балансится за счет случайных приоритетов
    //Поддерживает сумму(мин,макс) элементов в поддереве и нахождение суммы(мин,макс)на заданном отрезке.
    //
    public static class Node {
        public int key;
        public int prior;
        public int cnt;
        public Node left, right;

        Node(int key) {
            this.key = key;
            this.prior = rnd.nextInt();
            left = right = null;
            this.cnt = 1;
        }
    }

    public static int getCnt(Node t) {
        return t == null ? 0 : t.cnt;
    }

    public static void update(Node t) {
        if (t != null) {
            t.cnt = 1 + getCnt(t.left) + getCnt(t.right);
        }
    }

    public static void push(Node t) {
        if (t != null) {

        }
    }


    public static void pushAll(Node t) {
        if (t != null) {
            push(t);
            if (t.left != null) {
                pushAll(t.left);
            }
            if (t.right != null) {
                pushAll(t.right);
            }
        }
    }

    // Все с ключем < key в первое дерево, остальные во второе
    public static Pair<Node, Node> split(Node t, long key) {
        if (t == null) return new Pair<>(null, null);
        push(t);
        if (key > t.key) {
            Pair<Node, Node> p = split(t.right, key);
            t.right = p.first;
            update(t);
            return new Pair<>(t, p.second);
        } else {
            Pair<Node, Node> p = split(t.left, key);
            t.left = p.second;
            update(t);
            return new Pair<>(p.first, t);
        }
    }

    //SPLIT ПО НЕЯВНОМУ КЛЮЧУ
    //add for root = 0
    public static Pair<Node, Node> split(Node t, long key, int add) {
        push(t);
        if (t == null) return new Pair<>(null, null);
        int curKey = add + getCnt(t.left);
        if (key > curKey) { //идем в правое поддерево
            Pair<Node, Node> p = split(t.right, key, curKey + 1);
            t.right = p.first;
            update(t);
            return new Pair<>(t, p.second);
        } else { //идем в левое поддерево
            Pair<Node, Node> p = split(t.left, key, add);
            t.left = p.second;
            update(t);
            return new Pair<>(p.first, t);
        }
    }

    //Все ключи в первом дереве должны быть меньше ключей во втором
    public static Node merge(Node t1, Node t2) {
        push(t1);
        push(t2);
        if (t1 == null) return t2;
        if (t2 == null) return t1;
        if (t1.prior > t2.prior) {
            t1.right = merge(t1.right, t2);
            update(t1);
            return t1;
        } else {
            t2.left = merge(t1, t2.left);
            update(t2);
            return t2;
        }
    }

//    public static Node insert(Node t, Node newNode) {
//        if (t == null) {
//            t = newNode;
//        } else if (newNode.prior > t.prior) {
//            Pair<Node, Node> p = split(t, newNode.key);
//            newNode.left = p.first;
//            newNode.right = p.second;
//            t = newNode;
//        } else {
//            if (newNode.key < t.key) {
//                t.left = insert(t.left, newNode);
//            } else {
//                t.right = insert(t.right, newNode);
//            }
//        }
//        update(t);
//        return t;
//    }

    //Еще один insert, но вроде не такой быстрый
    public static Node insert(Node t, Node newNode) {
        if (t == null) {
            t = newNode;
        } else {
            Pair<Node, Node> p = split(t, newNode.key);
            t = merge(p.first, newNode);
            t = merge(t, p.second);
        }
        update(t);
        return t;
    }

    //Объединяет 2 разных дерева
    public static Node unite(Node t1, Node t2) {
        if (t1 == null) return t2;
        if (t2 == null) return t1;
        push(t1);
        push(t2);
        if (t1.prior < t2.prior) {
            Node c = t1;
            t1 = t2;
            t2 = c;
        }
        Pair<Node, Node> split1 = split(t2, t1.key);
        t1.left = unite(t1.left, split1.first);
        t1.right = unite(t1.right, split1.second);
        return t1;
    }

    public static Node remove(Node t, long key) {
        if (t == null) return null;
        if (t.key == key) {
            t = merge(t.left, t.right);
        } else {
            if (key < t.key) {
                t.left = remove(t.left, key);
            } else {
                t.right = remove(t.right, key);
            }
        }
        update(t);
        return t;
    }

    public static Node find(Node t, long key) {
        if (t == null) return null;
        if (t.key == key) return t;
        if (t.key < key) {
            return find(t.right, key);
        } else {
            return find(t.left, key);
        }
    }

    /**
     * Вырезает отрезок от i до j и вставляет в позицию k нового массива
     * (при k = 0 вставляет вначало)
     *
     * @param t Корень дерева
     * @param i Начало отрезка (включительно)
     * @param j Конец отрезка (включительно)
     * @param k Позиция вставки
     * @return Новое дерево
     */
    public static Node replaceSegment(Node t, int i, int j, int k) {
        //Вырезаем отрезок и склеиваем
        Pair<Node, Node> split1 = split(t, i, 0);
        Pair<Node, Node> split2 = split(split1.second, j - i + 1, 0);
        Node merge1 = merge(split1.first, split2.second);
        Node removedSegment = split2.first;

//      out.println("Array without removed:" + getString(merge1));
//      out.println("Removed Segment:" + getString(removedSegment));

        //разделяем и вставляем
        Pair<Node, Node> split3 = split(merge1, k, 0);
        Node merge2 = merge(split3.first, removedSegment);
        Node merge3 = merge(merge2, split3.second);

        return merge3;
    }

    public static Pair<Node, Integer> getCnt(Node t, int x) {
        Pair<Node, Node> split1 = split(t, x);

        int ans = split1.first == null ? 0 : split1.first.cnt;

        Node merge1 = merge(split1.first, split1.second);
        return new Pair<>(merge1, ans);
    }


    public static StringBuilder getKeysString(Node t) {
        if (t == null) return new StringBuilder();
        StringBuilder ans = new StringBuilder();
        if (t.left != null) ans.append(getKeysString(t.left));
        ans.append(t.key);
        ans.append(" ");
        if (t.right != null) ans.append(getKeysString(t.right));
        return ans;
    }

    public static class Pair<F, S> {
        public F first;
        public S second;

        Pair(F first, S second) {
            this.first = first;
            this.second = second;
        }

//        @Override
//        public int compareTo(Object o) {
//            return first.compareTo(((Pair)o).first);
//        }

        @Override
        public boolean equals(Object o) {
            if (!(o instanceof Main.Pair)) {
                return false;
            }
            Main.Pair<?, ?> p = (Main.Pair<?, ?>) o;
            return Objects.equals(p.first, first) && Objects.equals(p.second, second);
        }

        @Override
        public int hashCode() {
            return (first == null ? 0 : first.hashCode()) ^ (second == null ? 0 : second.hashCode());
        }
    }
}