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 gym{
	static class ftree{
		int n;
		int[]ft;
		ftree(int z){
			ft=new int[z+1];
			n=z;
		}
		void updatesum(int idx,int k) {
			while(idx<=n) {
				ft[idx]+=k;
				idx+=(idx&(-1*idx));
			}
			
		}
		int querysum(int idx) {
			int sum=0;
			while(idx>0) {
				sum+=ft[idx];
				idx-=(idx&(-1*idx));
			}
			return sum;
		}
	}
	static void main() throws Exception{
		int n=sc.nextInt();
		int[]in=sc.intArr(n);
		ftree ft=new ftree(n);
		HashMap<Integer, Integer>occAll=new HashMap<>(),curOcc=new HashMap<>(),compress=new HashMap<>();
		int[]tmp=new int[n];
		for(int i=0;i<n;i++) {
			tmp[i]=in[i];
		}
		shuffle(tmp);
		Arrays.sort(tmp);
		for(int i=0;i<tmp.length;i++) {
			compress.put(tmp[i], i+1);
		}
		for(int idx=0;idx<n;idx++) {
			int i=in[idx];
			occAll.put(compress.get(i), occAll.getOrDefault(compress.get(i), 0)+1);
		}
		long ans=0;
		for(int i=n-1;i>=0;i--) {
			int key=compress.get(in[i]);
			int aiOcc=curOcc.getOrDefault(key, 0);
			int fi=occAll.get(key)-aiOcc;
			ans+=ft.querysum(fi-1);
			aiOcc++;
			curOcc.put(key,aiOcc);
			
			int fj=aiOcc;
			ft.updatesum(fj, 1);
		}
		pw.println(ans);
	}
	public static void main(String[] args) throws Exception{
		pw=new PrintWriter(System.out);
		sc = new MScanner(System.in);
		int tc=1;
		while(tc-->0)main();
		pw.flush();
	}
	static PrintWriter pw;
	static MScanner  sc;
	static class MScanner {
		StringTokenizer st;
		BufferedReader br;
		public MScanner(InputStream system) {
			br = new BufferedReader(new InputStreamReader(system));
		}
 
		public MScanner(String file) throws Exception {
			br = new BufferedReader(new FileReader(file));
		}
 
		public String next() throws IOException {
			while (st == null || !st.hasMoreTokens())
				st = new StringTokenizer(br.readLine());
			return st.nextToken();
		}
		public int[] intArr(int n) throws IOException {
	        int[]in=new int[n];for(int i=0;i<n;i++)in[i]=nextInt();
	        return in;
		}
		public long[] longArr(int n) throws IOException {
	        long[]in=new long[n];for(int i=0;i<n;i++)in[i]=nextLong();
	        return in;
		}
		public int[] intSortedArr(int n) throws IOException {
	        int[]in=new int[n];for(int i=0;i<n;i++)in[i]=nextInt();
	        shuffle(in);
	        Arrays.sort(in);
	        return in;
		}
		public long[] longSortedArr(int n) throws IOException {
	        long[]in=new long[n];for(int i=0;i<n;i++)in[i]=nextLong();
	        shuffle(in);
	        Arrays.sort(in);
	        return in;
		}
		public Integer[] IntegerArr(int n) throws IOException {
	        Integer[]in=new Integer[n];for(int i=0;i<n;i++)in[i]=nextInt();
	        return in;
		}
		public Long[] LongArr(int n) throws IOException {
	        Long[]in=new Long[n];for(int i=0;i<n;i++)in[i]=nextLong();
	        return in;
		}
		public String nextLine() throws IOException {
			return br.readLine();
		}
 
		public int nextInt() throws IOException {
			return Integer.parseInt(next());
		}
 
		public double nextDouble() throws IOException {
			return Double.parseDouble(next());
		}
 
		public char nextChar() throws IOException {
			return next().charAt(0);
		}
 
		public long nextLong() throws IOException {
			return Long.parseLong(next());
		}
 
		public boolean ready() throws IOException {
			return br.ready();
		}
 
		public void waitForInput() throws InterruptedException {
			Thread.sleep(3000);
		}
	}
	static void shuffle(int[]in) {
		for(int i=0;i<in.length;i++) {
			int idx=(int)(Math.random()*in.length);
			int tmp=in[i];
			in[i]=in[idx];
			in[idx]=tmp;
		}
	}
	static void shuffle(long[]in) {
		for(int i=0;i<in.length;i++) {
			int idx=(int)(Math.random()*in.length);
			long tmp=in[i];
			in[i]=in[idx];
			in[idx]=tmp;
		}
	}
}
