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.awt.*;
import java.awt.event.*;
import java.awt.geom.*;
import java.io.*;
import java.math.*;
import java.text.*; 
import java.util.*;
import java.util.regex.*;

/*
  br = new BufferedReader(new FileReader("input.txt"));
  pw = new PrintWriter(new BufferedWriter(new FileWriter("output.txt")));
  br = new BufferedReader(new InputStreamReader(System.in));
  pw = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
 */


public class Main {
	private static BufferedReader br;
	private static StringTokenizer st;
	private static PrintWriter pw;

	public static void main(String[] args) throws IOException {
		br = new BufferedReader(new InputStreamReader(System.in));
		pw = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
		//int qq = 1;
		int qq = Integer.MAX_VALUE;
		//int qq = readInt();
		for(int casenum = 1; casenum <= qq; casenum++) {
			int n = readInt();
			int[] f = new int[n];
			int[] g = new int[n];
			int[] list = new int[n];
			for(int i = 0; i < n; i++) {
				list[i] = readInt();
			}
			init(n);
			Map<Integer, Integer> prefix = new HashMap<Integer, Integer>();
			for(int i = 0; i < n; i++) {
				inc(prefix, list[i]);
				f[i] = prefix.get(list[i]);
			}
			Map<Integer, Integer> suffix = new HashMap<Integer, Integer>();
			for(int i = n-1; i >= 0; i--) {
				inc(suffix, list[i]);
				g[i] = suffix.get(list[i]);
				update(g[i], 1);
			}
			long ret = 0;
			for(int i = 0; i < n; i++) {
				update(g[i], -1);
				ret += query(f[i]-1);
			}
			pw.println(ret);
		}
		exitImmediately();
	}

	public static void inc(Map<Integer, Integer> m, int k) {
		if(!m.containsKey(k)) {
			m.put(k, 0);
		}
		m.put(k, 1 + m.get(k));
	}
	
	static int[] tree;
	
	public static void init(int n) {
		tree = new int[n+5];
	}
	
	public static void update(int index, int val) {
		while(index < tree.length) {
			tree[index] += val;
			index += index & -index;
		}
	}
	
	public static int query(int index) {
		int ret = 0;
		while(index > 0) {
			ret += tree[index];
			index -= index & -index;
		}
		return ret;
	}
	
	private static void exitImmediately() {
		pw.close();
		System.exit(0);
	}

	private static long readLong() throws IOException {
		return Long.parseLong(nextToken());
	}

	private static double readDouble() throws IOException {
		return Double.parseDouble(nextToken());
	}

	private static int readInt() throws IOException {
		return Integer.parseInt(nextToken());
	}

	private static String nextLine() throws IOException  {
		if(!br.ready()) {
			exitImmediately();
		}
		st = null;
		return br.readLine();
	}

	private static String nextToken() throws IOException  {
		while(st == null || !st.hasMoreTokens())  {
			if(!br.ready()) {
				exitImmediately();
			}
			st = new StringTokenizer(br.readLine().trim());
		}
		return st.nextToken();
	}
}
