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.HashMap;
import java.util.Scanner;

public class PASHMAK_AND_PARMIDA_PROBLEM {

	public static long count = 0;
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		
		Scanner s = new Scanner(System.in);
		int n = s.nextInt();
		
		int[] arr = new int[n];
		int max = 0;
		for(int i=0;i<n;i++) {
			arr[i] = s.nextInt();
		}
		

		int[][] freq = new int[2][n];
		
		HashMap<Integer, Integer> map = new HashMap<>();
		
		for(int i=0;i<n;i++) {
			int v = arr[i];
			
			if(map.containsKey(v))
			{
				int c = map.get(v);
				freq[0][i] = c + 1;
				map.put(v, c + 1);
			}
			
			else {
				freq[0][i] = 1;
				map.put(v, 1);
			}
		}
		
		map = new HashMap<>();
		
		for(int i=n-1;i>=0;i--) {
			int v = arr[i];
			
			if(map.containsKey(v))
			{
				int c = map.get(v);
				freq[1][i] = c + 1;
				map.put(v, c + 1);
			}
			
			else {
				freq[1][i] = 1;
				map.put(v, 1);
			}
			
			max = Math.max(max, freq[1][i]);
		}
//		USING DIVIDE AND CONQUER:
//		getCount(freq, 0, n-1);
//		System.out.println(count);
		
//		USING FENWICK TREE:
		//System.out.println("max = "+max);
		int[] bit = new int[max + 1];
		//System.out.println(count);
		for(int i=n-1;i>=0;i--)
		{
			int sum = getSum(bit, freq[0][i] - 1);
			//System.out.println(sum);
			count += sum;
			update(bit, freq[1][i], 1);
		}
		
		System.out.println(count);
		
	}
	
	public static int getSum(int[] bit, int index) {
		int sum = 0;
		while(index > 0) {
			sum += bit[index];
			index -= (index & (-index));
		}
		
		return sum;
	}
	
	public static void update(int[] bit, int index, int val) {
		int n = bit.length;
		
		while(index < n) {
			bit[index] += val;
			index += (index & (-index));
		}
	}
	
	public static int[][] getCount(int[][] arr, int low, int high) {
		int n = high - low + 1;
		if(low == high) {
			int[][] ar = new int[2][1];
			ar[0][0] = arr[0][low];
			ar[1][0] = arr[1][low];
			
			return ar;
		}
		
		int mid = (low + high)/2;
		int[][] ar1 = getCount(arr, low, mid);
		int[][] ar2 = getCount(arr, mid + 1, high);
		
		int i = 0, j = 0;
		
		int[][] ar = new int[2][n];
		//System.out.println(n);
//		print(ar1[0]);
//		print(ar2[1]);
		while(i < ar1[0].length && j < ar2[0].length) {
			//System.out.println(i+" "+j);
			if(ar1[0][i] <= ar2[1][j]) {
				count += j;
				i++;
			}
				
			else {
				j++;
			}
			
		}
		
		while(i < ar1[0].length) {
			count += ar2[0].length;
			//System.out.println("count = "+count);
			i++;
		}
			
		
		merge(ar[0], ar1[0], ar2[0]);
		merge(ar[1], ar1[1], ar2[1]);
		
		return ar;
	}
	
	public static void merge(int[] ar, int[] ar1, int[] ar2) {
		int index = 0, i = 0, j = 0;
		
		while(i < ar1.length && j < ar2.length) {
			if(ar1[i] < ar2[j])
			{
				ar[index++] = ar1[i++];
			}
			
			else 
			{
				ar[index++] = ar2[j++];
			}
		}
		
		while(i < ar1.length) {
			ar[index++] = ar1[i++];
		}
		
		while(j < ar2.length) {
			ar[index++] = ar2[j++];
		}
	}
	
	public static void print(int[] arr) {
		for(int i=0;i<arr.length;i++)
			System.out.print(arr[i]+" ");
		
		System.out.println();
	}

}
