World is Exploding

Time Limit: 2000/1000 MS (Java/Others)

Memory Limit: 65536/65536 K (Java/Others)

Description

Given a sequence A with length n,count how many quadruple (a,b,c,d) satisfies: $a \neq b \neq c \neq d, 1 \leq a < b \leq n, 1 \leq c < d \leq n, A_{a} < A_{b}, A_{c} > A_{d}$.

Input

The input consists of multiple test cases.
Each test case begin with an integer n in a single line.

The next line contains n integers $A_{1},A_{2}\cdots A_{n}$.
$1 \leq n \leq 50000$
$0 \leq A_{i} \leq 1e9$

Output

For each test case,output a line contains an integer.

Sample Input

4 2 4 1 3 4 1 2 3 4

Sample Output

1 0

Hint

wange2014

Source

2016 Multi-University Training Contest 5

提交代码