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 Practice{
 public static void main(String[] args) {
     FastReader fs=new FastReader();
     PrintWriter out=new PrintWriter(System.out);
     int t=1;
     //t=fs.nextInt();
     for(int i=1;i<=t;i++) {
     	Practice m=new Practice();
         m.solve(i,out,fs);
     }
     out.close();
 } 
  public void solve(int test,PrintWriter out,FastReader fs){
	int n=fs.nextInt();
	int a[]=fs.nextIntArray(n);
	HashMap<Integer,Integer> hm= new HashMap<Integer,Integer>();
	int feq[]=new int[n+1];
	int end[]=new int[n];
	for(int i=n-1;i>=0;i--) {
		hm.put(a[i],hm.getOrDefault(a[i], 0)+1);
		feq[hm.get(a[i])]++;
		end[i]=hm.get(a[i]); 
	}
	SegmentTree st=new SegmentTree(n);
	st.build(1,feq,1,n);
	hm= new HashMap<Integer,Integer>();
	long ans=0;
	int index=0;
	for(int i:a) {
		hm.put(i,hm.getOrDefault(i, 0)+1);
		int count=hm.get(i);
		st.update(1, 1, n, end[index++]);
		ans+=st.sum(1, 1, n, 1, count-1);
	}
	out.println(ans);
 }
}
class SegmentTree{
	int t[];
	SegmentTree(int n){
		t=new int[4*n];
	}
	void build(int v,int a[],int l,int r) {
		if(l>r)return;
		if(l==r) {
			t[v]=a[l];
			return;
		}
		int tm=(l+r)/2;
		build(2*v,a,l,tm);
		build(2*v+1,a,tm+1,r);
		t[v]=t[2*v]+t[2*v+1];
	}
	int sum(int v,int tl,int tr,int l,int r) {
		if(l>r)return 0;
		if(tl==l&&tr==r) return t[v];
		int mid=(tl+tr)/2;
		return sum(2*v,tl,mid,l,Integer.min(r, mid))+sum(2*v+1,mid+1,tr,Integer.max(l, mid+1),r); 
	}
	void update(int v,int tl,int tr,int pos) {
		if(tl==tr) {
			t[v]--;
			return;
		}
		int mid=(tl+tr)/2;
		if(pos<=mid)
			update(2*v,tl,mid,pos);
		else
			update(2*v+1,mid+1,tr,pos);
		t[v]=t[2*v]+t[2*v+1];
	}
}
class FastReader{
 BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
 StringTokenizer st=new StringTokenizer("");  
 String next(){
     while(!st.hasMoreTokens()){
         try {
             st=new StringTokenizer(br.readLine()); 
         } catch (IOException e) {
				e.printStackTrace();
			}
     }
     return st.nextToken();
 }
 int nextInt(){
     return Integer.parseInt(next());
 }
 long nextLong(){
     return Long.parseLong(next());
 }
 int[] nextIntArray(int n){ 
     int a[]=new int[n];
     for(int i=0;i<n;i++)a[i]=nextInt();
     return a;
 } 
 long[] nextLongArray(int n){
     long a[]=new long[n];
     for(int i=0;i<n;i++)a[i]=nextInt();
     return a;
 }
 char[] nextCharArray(){
     char a[]=next().toCharArray();
     return a;
 }
}