Пожалуйста, прочтите новое правило об ограничении использования AI-инструментов. ×

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

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

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

Шапур считает, что степень слабости армии равна количеству таких троек 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