Изменения рейтингов за последние раунды временно удалены. Скоро они будут возвращены. ×

E. Противник слаб
ограничение по времени на тест
5 seconds
ограничение по памяти на тест
256 megabytes
ввод
стандартный ввод
вывод
стандартный вывод

Римляне снова наступают. На этот раз их гораздо больше чем персов, но Шапур готов победить их. Он говорит: «Лев никогда не испугается сотни овец».

Не смотря на это, Шапур должен найти слабость римской армии чтобы победить ее. Как вы помните, Шапур — математик, поэтому он определяет насколько слаба армии как число — степень слабости.

Шапур считает, что степень слабости армии равна количеству таких троек i, j, k, что i < j < k и ai > aj > ak, где ax — сила человека, стоящего в строю на месте с номером x. Армия римлян обладает одной особенностью — силы всех людей в ней различны.

Помогите Шапуру узнать, насколько слаба армия римлян.

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

В первой строке записано одно целое число n (3 ≤ n ≤ 106) — количество солдат в римской армии. Следующая строка содержит n различных целых чисел ai (1 ≤ i ≤ n, 1 ≤ ai ≤ 109) — силы людей в римской армии.

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

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

Пожалуйста, не используйте спецификатор %lld для чтения или записи 64-х битовых чисел на С++. Рекомендуется использовать поток cout (также вы можете использовать спецификатор %I64d).

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