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.InputStreamReader;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Random;
import java.util.StringTokenizer;

public class Solution{
	
	
	
	
    public static void main(String[] args) throws IOException {
     
    	FastScanner fs = new FastScanner();
    	PrintWriter out = new PrintWriter(System.out);
    	
    		
    		
    	int tt = 1;
    	while(tt-->0) {
    		
    		int n = fs.nextInt();
    		int[] a = fs.readArray(n);
    		
    		HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
    		int[] pre = new int[n];
    		
    		for(int i=0;i<n;i++) {
    			map.put(a[i], map.getOrDefault(a[i], 0)+1);
    			pre[i] = map.get(a[i]);
    		}
    		
    		map.clear();
    		
    		Ftree ftree = new Ftree(n+1);
    		
    		long ans = 0;
    		
    		for(int i=n-1;i>=0;i--) {
    			ans += ftree.query(pre[i]-1);
    			map.put(a[i], map.getOrDefault(a[i], 0)+1);
    			ftree.update(map.get(a[i]), 1);
    			int x = 1;
    		}
    		
    		out.println(ans);
    		
    		
    		
    		
    		
    		
    	}
    	
    		
    		
    		
    	out.close();
    		
    }
    
   
    static class Ftree{
    	int[] bit;
    	int n;
    	
    	Ftree(int n){
    		this.n = n;
    		bit = new int[n];
    	}
    	
    	void update(int ind, int val) {
    		while(ind<n) {
    			bit[ind] += val;
    			ind += ind&(-ind);
    		}
    	}
    	
    	long query(int ind) {
    		long sum=0;
    		while(ind>0) {
    			sum += bit[ind];
    			ind -= ind&(-ind);
    		}
    		return sum;
    	}
    	
    }
    
    
    
  
    
    
    static final Random random=new Random();
    	
    static void ruffleSort(int[] a) {
    	int n=a.length;//shuffle, then sort 
    	for (int i=0; i<n; i++) {
    		int oi=random.nextInt(n); int temp=a[oi];
    		a[oi]=a[i]; a[i]=temp;
    	}
    	Arrays.sort(a);
    }
   
  
    
    	
    	
    static class FastScanner{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer("");
     
    	public String next(){
    		while(!st.hasMoreElements()){
    			try{
    				st = new StringTokenizer(br.readLine());
    			} catch(IOException e){
    				e.printStackTrace();
    			}
    		}
    		return st.nextToken();
    	}
    		
    	public String nextLine() throws IOException {
    		return br.readLine();
    	}
    		
    	public int nextInt(){
    		return Integer.parseInt(next());
    	}
     
    	public int[] readArray(int n){
    		int[] a = new int[n];
    		for(int i=0;i<n;i++)
    			a[i] = nextInt();
    		return a;
    	}
    		
    	public long nextLong() {
    		return Long.parseLong(next());
    	}
    		
    	public char nextChar() {
    		return next().toCharArray()[0];
    	}
    }
   	
}