Обезьянка подарила Юре массив a из n целых чисел. Юра сразу же захотел определить привлекательность этого массива. Он считает, что привлекательность массива - это количество троек индексов i, j, k, таких что 1 ≤ i < j < k ≤ n и a[i]
< a[j]
< a[k]
. Но Юра еще не умеет программировать, поэтому попросил помощи у Вас.
Помогите Юре узнать привлекательность массива.
Первая строка содержит одно число n (1 ≤ n ≤ 10^5
) - размер массива. Вторая строка содержит n неотрицательных целых чисел - элементы массива. Все элементы массива не превосходят 10^6
.
Выведите одно число - привлекательность массива.