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.*;
import java.math.*;
 
public class Main {


    public class BIT{

        int n;
        int[] bit;

        public BIT(int n){
            
            this.n = n;
            this.bit = new int[n + 1]; // bit are 1-based
        
        }

        public long query(int idx){
        
            long res = 0;
            while(idx != 0){
                res += bit[idx];
                idx -= (idx & (-idx));
            }
            return res;
        }

        public void update(int idx, int val){
        
            while(idx < n + 1){
                bit[idx] += val;
                idx += (idx & (- idx));
            }
        }
    }

    public void solve() throws IOException{

        int n = in.nextInt();
        int[] aa = new int[n];
        HashMap<Integer, Integer> map = new HashMap<>();
        int index = 1;
        for(int i = 0; i < n; i++){
            int num = in.nextInt();
            if(map.containsKey(num)){
                aa[i] = map.get(num);
            }else{
                aa[i] = index;
                map.put(num, index);
                index++;
            }
        }

        int[] lCnt = new int[n];
        int[] rCnt = new int[n];
        
        HashMap<Integer, Integer> cntSoFar = new HashMap<>();
        for(int i = 0; i < n; i++){ // inclusive
            cntSoFar.put(aa[i], cntSoFar.getOrDefault(aa[i], 0) + 1);
            lCnt[i] = cntSoFar.get(aa[i]);
        }
        cntSoFar.clear();
        for(int i = n - 1; i >= 0; i--){
            cntSoFar.put(aa[i], cntSoFar.getOrDefault(aa[i], 0) + 1);
            rCnt[i] = cntSoFar.get(aa[i]);
        }

        BIT bit = new BIT(1000001);
        long res = 0;
        for(int i = n - 1; i >= 0; i--){

            int cur = lCnt[i]; // how many are smaller
            res += bit.query(cur - 1); // strictly smaller
            bit.update(rCnt[i], 1); // add the count of cur and all above
        
            //out.println("current value " + cur + " current res " + res);
        }

        out.println(res);



    }

    public BigInteger gcdBigInt(BigInteger a, BigInteger b){

        if(a.compareTo(BigInteger.valueOf(0L)) == 0){
            return b;
        }else{
            return gcdBigInt(b.mod(a), a);
        }

    }

 
    FastScanner in;
    PrintWriter out;
 
    static class FastScanner {
 
        BufferedReader br;
        StringTokenizer st;
 
        FastScanner(InputStream in) {
            br = new BufferedReader(new InputStreamReader(in));
            st = null;
        }
 
        String next() throws IOException {
            while (st == null || !st.hasMoreTokens())
                st = new StringTokenizer(br.readLine());
            return st.nextToken();
        }
 
        String nextLine() throws IOException {
            if (st == null || !st.hasMoreTokens())
                return br.readLine();
            StringBuilder result = new StringBuilder(st.nextToken());
            while (st.hasMoreTokens()) {
                result.append(" ");
                result.append(st.nextToken());
            }
            return result.toString();
        }
 
        int nextInt() throws IOException {
            return Integer.parseInt(next());
        }
 
        long nextLong() throws IOException {
            return Long.parseLong(next());
        }
 
        double nextDouble() throws IOException {
            return Double.parseDouble(next());
        }
 
    }
 
    void run() throws IOException {
        in = new FastScanner(System.in);
        out = new PrintWriter(System.out, false);
        solve();
        out.close();
    }
 
    public static void main(String[] args) throws IOException{
        new Main().run();
    }
 
    public void printArr(int[] arr){
        for(int i = 0; i < arr.length; i++){
            out.print(arr[i] + " ");
        }
        out.println();
    }
 
    public long gcd(long a, long b){
        if(a == 0) return b;
        return gcd(b % a, a);
    }

    public boolean isPrime(long num){

        if(num == 0 || num == 1){
            return false;
        }

        for(int i = 2; i * i <= num; i++){
            if(num % i == 0){
                return false;
            }
        }

        return true;
    }

    public class Pair<A, B>{
        public A x; 
        public B y;

        Pair(A x, B y){
            this.x = x;
            this.y = y;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Pair<?, ?> pair = (Pair<?, ?>) o;
            if (!x.equals(pair.x)) return false;
            return y.equals(pair.y);
        }

        @Override
        public int hashCode() {
            int result = x.hashCode();
            result = 31 * result + y.hashCode();
            return result;
        }

    }

    class Tuple{
        int x; int y; int z;
        Tuple(int ix, int iy, int iz){
            x = ix;
            y = iy;
            z = iz;
        }
    }
}
