Migrated from Lutece 384 Crazy Thairs

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

These days, Sempr is crazed on one problem named Crazy Thair. Given $N$ ($1\leq N\leq 50000$) numbers, and their absolute value are no more than $1000000000$. Crazy Thair is a group of $5$ numbers {$i, j, k, l, m$} satisfying:

1. $1\leq i < j < k < l < m\leq N$
2. $A_i < A_j < A_k < A_l < A_m$

For example, in the sequence {$2, 1, 3, 4, 5, 7, 6$},there are four Crazy Thair groups: {$1, 3, 4, 5, 6$}, {$2, 3, 4, 5, 6$}, {$1, 3, 4, 5, 7$} and {$2, 3, 4, 5, 7$}.

Could you help Sempr to count how many Crazy Thairs in the sequence?

Input

Input contains several test cases. Each test case begins with a line containing a number $N$, followed by a line containing $N$ numbers.

Output

Output the amount of Crazy Thairs in each sequence.

Samples

5
1 2 3 4 5
7
2 1 3 4 5 7 6
7
1 2 3 4 5 6 7

1
4
21

Note

The data used in this problem is unofficial data prepared by pfctgeorge. So any mistake here does not imply mistake in the offcial judge data.

Resources

POJ Monthly--2007.09.09, tdzl2003