Обезьянка подарила Юре массив a из n целых чисел. Юра сразу же захотел определить привлекательность этого массива. Он считает, что привлекательность массива - это количество троек индексов i, j, k, таких что 1 ≤ i < j < k  ≤ n и ai < aj < ak. Но Юра еще не умеет программировать, поэтому попросил помощи у Вас.

Помогите Юре узнать привлекательность массива.

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

Первая строка содержит одно число n (1 ≤ n ≤ 105) - размер массива. Вторая строка содержит n неотрицательных целых чисел - элементы массива. Все элементы массива не превосходят 106.

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

Выведите одно число - привлекательность массива.