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
//coderadi
import java.io.*;
import java.util.*;

public class A {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int[] ar = new int[n];
		int[] left = new int[n];
		int[] right = new int[n];
		for (int i=0; i<n; i++) {
			ar[i] = sc.nextInt();
		}
		//make left
		HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
		for(int i=0; i<n; i++){
			int a = ar[i];
			if(map.containsKey(a)){
				int val = map.get(a);
				map.put(a, val + 1);
				left[i] = val + 1;
			}else{
				map.put(ar[i], 1);
				left[i] = 1;
			}
		}

		map = new HashMap<Integer, Integer>();
		for (int i=n-1; i>=0; i--) {
			int a = ar[i];
			if(map.containsKey(a)){
				int val = map.get(a);
				map.put(a, val + 1);
				right[i] = val + 1;
			}else{
				map.put(ar[i], 1);
				right[i] = 1;
			}		
		}

		AVLTree t = new AVLTree();
		long pair = 0;
		for(int i=n-2, j = n-1; i>=0; i--, j--){
			t.insert(right[j]);
			//System.out.println(right[j]);
			pair += t.cal(left[i]);
		}
		System.out.println(pair);
	}
}

class AVLTree{
	Node root;

	public int cal(int val){
		return calUtil(root, val, 0);
	}
	private int calUtil(Node curr, int val, int count){
		if(curr == null)
			return count;
		if(curr.val == val){
			return (curr.lCount + count);
		}
		if(curr.val > val){
			return calUtil(curr.left, val, count);
		}
		if(curr.val < val){
			return (curr.lCount + curr.count + calUtil(curr.right, val, count));
		}

		return -1;
	}

	public void insert(int val){
		root = insertUitl(root, val);
	}

	private Node insertUitl(Node curr, int val){
		if(curr == null){
			curr = new Node(val);
			return curr;
		}

		if(curr.val == val){
			curr.count++;
			return curr;
		}
		else if(curr.val > val){
			curr.lCount++;
			curr.left = insertUitl(curr.left, val);
		}
		else if(curr.val < val){
			curr.rCount++;
			curr.right = insertUitl(curr.right, val);
		}
		curr.height = Math.max(getHeight(curr.left), getHeight(curr.right)) + 1;
		curr.balFactor = getBal(curr);
		int bal = curr.balFactor;
		if(bal > 1 && val > curr.right.val)
			return leftRotate(curr);
		if(bal > 1 && val < curr.right.val){
			curr.right = rightRotate(curr.right);
			return leftRotate(curr);
		}
		if(bal < -1 && val < curr.left.val){
			return rightRotate(curr);
		}
		if(bal < -1 && val > curr.left.val){
			curr.left = leftRotate(curr.left);
			return rightRotate(curr);
		}

		return curr;
	}

	private Node leftRotate(Node x){
		Node y = x.right;
		Node t3 = y.left;
		x.right = t3;
		y.left = x;

		x.lCount = getSize(x.left);
		x.rCount = getSize(x.right);
		x.height = Math.max(getHeight(x.left), getHeight(x.right)) + 1;


		y.lCount = getSize(y.left);
		y.rCount = (getSize(y.right));
		y.height = Math.max(getHeight(y.left), getHeight(y.right)) + 1;

		x.balFactor = getBal(x);
		y.balFactor = getBal(y);

		return y;
	}

	private Node rightRotate(Node x){
		Node y = x.left;
		x.left = y.right;
		y.right = x;

		x.lCount = getSize(x.left);
		x.rCount = getSize(x.right);
		x.height = Math.max(getHeight(x.left), getHeight(x.right)) + 1;


		y.lCount = getSize(y.left);
		y.rCount = (getSize(y.right));
		y.height = Math.max(getHeight(y.left), getHeight(y.right)) + 1;

		x.balFactor = getBal(x);
		y.balFactor = getBal(y);

		return y;
	}



	//helper methods
	private static int getSize(Node curr){
		if(curr == null)
			return 0;
		return (curr.lCount + curr.rCount + curr.count);
	}

	private int getHeight(Node curr){
		if(curr == null)
			return 0;
		else
			return curr.height;
	}

	private int getBal(Node curr){
		return getHeight(curr.right) - getHeight(curr.left);
	}
}

class Node{
	int val;
	int count; 		//holds the total number of this val
	int lCount, rCount; //number of nodes in right and leftTree
	Node left, right; 	//pointer to the left and right subtree
	int height, balFactor;	//height and balance factor
	Node(int val){
		this.val = val; count = 1; lCount = 0; rCount = 0;
		left = null; right = null; height = 1; balFactor = 0;
	}

	public int size(){
		return (count + lCount + rCount);
	}
}