D. Задача Пашмака и Пармиды
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

Пармида — умная девушка, в этом году она хочет принять участие в олимпиаде. Конечно, она хочет, чтобы ее парень тоже был умным! Девушка приготовила следующую тестовую задачу для Пашмака.

Задана последовательность a, состоящая из n целых чисел: a1, a2, ..., an. Обозначим за f(l, r, x) количество таких индексов k, что: l ≤ k ≤ r и x = ak. Требуется посчитать количество таких пар индексов i, j (1 ≤ i < j ≤ n), что f(1, i, ai) > f(j, n, aj).

Помогите Пашмаку с этой задачей.

Входные данные

В первой строке записано целое число n (1 ≤ n ≤ 106). Во второй строке записано n целых чисел через пробел a1, a2, ..., an (1 ≤ ai ≤ 109).

Выходные данные

Выведите единственное целое число — ответ на задачу.

Примеры
Входные данные
7
1 2 1 1 2 2 1
Выходные данные
8
Входные данные
3
1 1 1
Выходные данные
1
Входные данные
5
1 2 3 4 5
Выходные данные
0