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.util.*;
import java.io.*;
public class Solution implements Runnable {
    FastScanner sc;
    PrintWriter pw;
    final class FastScanner {
        BufferedReader br;
        StringTokenizer st;
 
        public FastScanner() {
            try {
                br = new BufferedReader(new InputStreamReader(System.in));
                st = new StringTokenizer(br.readLine());
            } catch (Exception e) {
                e.printStackTrace();
            }
        }
 
        public long nlo() {
            return Long.parseLong(next());
        }
 
        public String next() {
            if (st.hasMoreTokens()) return st.nextToken();
            try {
                st = new StringTokenizer(br.readLine());
            } catch (Exception e) {
                e.printStackTrace();
            }
            return st.nextToken();
        }
 
        public int ni() {
            return Integer.parseInt(next());
        }
 
        public String nli() {
            String line = "";
            if (st.hasMoreTokens()) line = st.nextToken();
            else try {
                return br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            while (st.hasMoreTokens()) line += " " + st.nextToken();
            return line;
        }
 
        public double nd() {
            return Double.parseDouble(next());
        }
    }
    public static void main(String[] args) throws Exception
    {
        new Thread(null,new Solution(),"codeforces",1<<28).start();
    }
    public void run()
    {
        sc=new FastScanner();
        pw=new PrintWriter(System.out);
        try{
        solve();}
        catch(Exception e)
        {
            pw.println(e);
        }
        pw.flush();
        pw.close();
    }
    public long gcd(long a,long b)
    {
        return b==0L?a:gcd(b,a%b);
    }
    public long ppow(long a,long b,long mod)
    {
        if(b==0L)
        return 1L;
        long tmp=1;
        while(b>1L)
        {
            if((b&1L)==1)
            tmp*=a;
            a*=a;
            a%=mod;
            tmp%=mod;
            b>>=1;
        }
        return (tmp*a)%mod;
    }
    public long pow(long a,long b)
    {
        if(b==0L)
        return 1L;
        long tmp=1;
        while(b>1L)
        {
            if((b&1L)==1)
            tmp*=a;
            a*=a;
            b>>=1;
        }
        return (tmp*a);
    }
    public  int gcd(int x,int y)
    {
        return y==0?x:gcd(y,x%y);
    }
   
    //////////////////////////////////
    /////////////  LOGIC  ///////////
    ////////////////////////////////
    public Integer[] ans,count;
    public boolean res = true;
    public void solve() throws Exception{
        int n=sc.ni();
        int[] prr=new int[n];
        int[] srr=new int[n];
        int[] arr=new int[n];
        HashMap<Integer,Integer> map=new HashMap();
        for(int i=0;i<n;i++){
            arr[i]=sc.ni();
            int x=arr[i];
            if(map.containsKey(x))
                map.put(x,map.get(x)+1);
            else
                map.put(x,1);
            prr[i]=map.get(x);
        }
        map=new HashMap();
        for(int i=n-1;i>=0;i--){
            int x=arr[i];
            if(map.containsKey(x))
                map.put(x,map.get(x)+1);
            else
                map.put(x,1);
            srr[i]=map.get(x);
        }
        int[] seg=new int[4*(n+1)+1];
        update(prr[0],0,n+1,1,seg);
        long ans=0;
        for(int i=1;i<n;i++){
            long temp=query(srr[i]+1,n,seg,1,0,n+1);
            ans+=temp;
            update(prr[i],0,n+1,1,seg);
        }
        pw.println(ans);
    }
    public void update(int p,int st,int end,int ind,int[] seg){
        if(p<st||p>end)
        return;
        if(st==end&&st==p){
            seg[ind]++;
            return;
        }
        update(p,st,(st+end)/2,2*ind,seg);
        update(p,(st+end)/2+1,end,2*ind+1,seg);
        seg[ind]=seg[2*ind]+seg[2*ind+1];
    }
    public int query(int l,int r,int[] seg,int ind,int st,int en){
        if(r<st||l>en)
        return 0;
        if(l<=st&&r>=en)
        return seg[ind];
        else return query(l,r,seg,2*ind,st,(st+en)/2)+query(l,r,seg,2*ind+1,(st+en)/2+1,en);
    }
}