Problem Description

Takahashi has an integer sequence \( A \) consisting of \( N \) elements: \( A_1, A_2, \cdots, A_N \).

Find the number of tuples \( (i, j, k) \) \( (1 \leq i < j < k \leq N) \) that satisfy \( A_i < A_j > A_k \).

Input Format

The input is given from the standard input in the following format:

\( N \) \( A_1 \) \( A_2 \) \( \cdots \) \( A_N \)

Output Format

Output the number of tuples \( (i, j, k) \) \( (1 \leq i < j < k \leq N) \) that satisfy \( A_i < A_j > A_k \).

Sample Input and Output

Sample Input #1

4
1 2 3 2

Sample Output #1

2

Sample Input #2

3
2 2 2

Sample Output #2

0

Sample Input #3

10
0 7 7 6 9 8 1 3 2 0

Sample Output #3

57

Notes/Hints

Constraints

• \( 3 \leq N \leq 5000 \)
• \( 0 \leq A_i \leq 10^9 \)
• All inputs are integers.

Sample Explanation 1

The tuples satisfying the condition are \( (i, j, k) = (1, 3, 4), (2, 3, 4) \), totaling 2.

Sample Explanation 2

There are no tuples \( (i, j, k) \) that satisfy \( A_i < A_j > A_k \).

见题面 Input 部分

见题面 Output 部分