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

Допоможіть Юрку дізнатись привабливість масиву.

Вхідні дані

У першому рядку задано одне число n (1 ≤ n ≤ 105) - розмір масиву. У другому рядку міститься n невід'ємних цілих чисел - елементи масиву. Всі елементи масиву не перевищують 106.

Вихідні дані

Виведіть одне число - привабливість масиву.