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

// Problem: D. Pashmak and Parmida's problem
// Contest: Codeforces - Codeforces Round #261 (Div. 2)
// URL: https://codeforces.com/contest/459/problem/D
// Memory Limit: 256 MB
// Time Limit: 3000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)

import java.io.*;
import java.util.*;

public class Main {
    private static PrintWriter pw = new PrintWriter(System.out);
    private static InputReader sc = new InputReader();

    static class InputReader{
        private static BufferedReader r = new BufferedReader(new InputStreamReader(System.in));
        private static StringTokenizer tk;

        private void next()throws IOException{
            if(tk == null || !tk.hasMoreTokens())   
                tk = new StringTokenizer(r.readLine());
        }

        private int nextInt()throws IOException{
            next();
            return Integer.parseInt(tk.nextToken());
        }

        private int[] intArray(int n)throws IOException{
            next();
            int arr[] = new int[n];

            for(int i=0; i<n; i++)
                arr[i] = nextInt();

            return arr;
        }
    }

    public static void main(String args[])throws IOException{
        int t = 1;
        while(t-->0)    solve();
        pw.flush();
        pw.close();
    }
    
    static class Node{
    	int begin, end, data;
    	Node left, right;
    	
    	Node(int b, int e){
    		begin = b;
    		end = e;
    		
    		if(begin != end){
    			int mid = (begin + end)/2;
    			
    			left = new Node(begin, mid);
    			right = new Node(mid+1, end);
    		}
    	} 
    	
    	void update(int index, int val){
    		if(index < begin || end < index)
    			return;
    			
    		if(begin == end){
    			data += val;
    			return;
    		}
    		
    		left.update(index, val);
    		right.update(index, val);
    		
    		data = left.data + right.data;
    	}
    	
    	int query(int l, int r){
    		if(l > r || begin > r || l > end)
    			return 0;
    			
    		if(l <= begin && end <= r)
    			return data;
    			
    		return left.query(l, r) + right.query(l, r);
    	}
    }

    private static void solve()throws IOException{
		int n = sc.nextInt(), pre[] = new int[n], a[] = sc.intArray(n);
		
		HashMap<Integer, Integer> map = new HashMap<>();
		
		for(int i=0; i<n; i++){
			int oldVal = map.getOrDefault(a[i], 0);
			pre[i] = oldVal + 1;
			map.put(a[i], oldVal+1);
		}
		
		Node root = new Node(0, n);
		map.clear();
		map.put(a[n-1], 1);
		root.update(1, 1);
		
		long ans = 0;
		
		for(int i=n-2; i>=0; i--){
			int lim = pre[i];
			ans += root.query(1, lim-1);
			
			int oldVal = map.getOrDefault(a[i], 0);
			
			root.update(oldVal+1, 1);
			map.put(a[i], oldVal + 1);
		}
		
		pw.println(+ans);
    }
}