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
/* one segment tree a day, keeps Ossama away */

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.StringTokenizer;

public class Main
{

	public static void main(String[] args) throws IOException
	{

		Main main = new Main();
		main.read();
	}

	/* IO */
	private InputReader in;
	private StringBuilder ans;

	/* fields */
	private int n;
	private int[] arr;
	private long[] tree;

	private void read() throws IOException
	{
		// streams
		boolean file = false;
		if (file)
			in = new InputReader(new FileInputStream("Input.txt"));
		else
			in = new InputReader(System.in);
		ans = new StringBuilder();

		// read
		n = Integer.parseInt(in.next());
		arr = new int[n];
		for (int i = 0; i < n; i++)
			arr[i] = Integer.parseInt(in.next());

		// solve
		System.out.println(solve());

	}

	private long solve()
	{
		// compress and create left count, right count array
		compress();
		int[] count = new int[n];
		int[] left = new int[n];
		for (int i = 0; i < n; i++)
			left[i] = ++count[arr[i]];
		count = new int[n];
		int[] right = new int[n];
		for (int i = n - 1; i >= 0; i--)
			right[i] = ++count[arr[i]];

		// hoppa segment tree
		tree = new long[4 * (n + 1)];
		long sum = 0;
		for (int i = 0; i < n; i++)
		{
			sum += queryTree(1, 1, n, right[i] + 1, n);
			updateTree(1, 1, n, left[i], left[i], 1);
		}
		return sum;
	}

	private void compress()
	{
		int curr = 0;
		HashMap<Integer, Integer> m = new HashMap<>();
		for (int i = 0; i < n; i++)
			if (!m.containsKey(arr[i]))
				m.put(arr[i], curr++);
		for (int i = 0; i < n; i++)
			arr[i] = m.get(arr[i]);

	}

	void updateTree(int node, int a, int b, int i, int j, int value)
	{
		if (a > b || a > j || b < i)
			return;

		if (a == b)
		{
			tree[node] += value;
			return;
		}

		int mid = (a + b) / 2;
		updateTree(node * 2, a, mid, i, j, value);
		updateTree(node * 2 + 1, mid + 1, b, i, j, value);
		tree[node] = tree[node * 2] + tree[node * 2 + 1];
	}

	long queryTree(int node, int a, int b, int i, int j)
	{
		if (a > b || a > j || b < i)
			return 0;
		if (a >= i && b <= j)
			return tree[node];

		int mid = (a + b) / 2;
		long q1 = queryTree(node * 2, a, mid, i, j);
		long q2 = queryTree(1 + node * 2, mid + 1, b, i, j);
		return q1 + q2;
	}

}

class InputReader
{
	public BufferedReader reader;
	public StringTokenizer tokenizer;

	public InputReader(InputStream stream)
	{
		reader = new BufferedReader(new InputStreamReader(stream), 32768);
		tokenizer = null;
	}

	public String next()
	{
		while (tokenizer == null || !tokenizer.hasMoreTokens())
		{
			try
			{
				tokenizer = new StringTokenizer(reader.readLine());
			} catch (IOException e)
			{
				throw new RuntimeException(e);
			}
		}
		return tokenizer.nextToken();
	}

}
