Пармида — умная девушка, в этом году она хочет принять участие в олимпиаде. Конечно, она хочет, чтобы ее парень тоже был умным! Девушка приготовила следующую тестовую задачу для Пашмака.
Задана последовательность 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).
Помогите Пашмаку с этой задачей.