"Antifan T_T" Zone
After 4 successful shows, PKL decided to add an extra show to please her fans and antifans. This time, she even gave the antifans special treatment by opening a new ticket tier, Antifan (T_T), with \(N\) seats reserved just for them.
To make it even harder for people in the blind spots to see the LED screen, she decided to change the heights of the seats. After the change, the seat heights are \(h_1, h_2, ..., h_N\) in order.
But now, this row of seats has stolen the spotlight because it's the most unique one. Many people say that for every choice of 3 seats \(i,j,k \ (1\le i < j < k \le N)\) where the left seat is lower than the right seat, and the right seat is lower than the middle seat \((h_i < h_k < h_j)\), the virality of this row increases by 1.
Help PKL find the virality of this row of seats so she can plan her next move.
Input
- The first line contains a positive integer \(N \ (3\le N \le 3\times 10^5)\);
- The next line contains \(N\) integers \(h_i \ (1\le h_i \le N)\); all values \(h_i\) are distinct.
Output
- A single integer, the answer to the problem.
Scoring
- Subtask 1 (30%): \(N \le 10^2\).
- Subtask 2 (40%): \(N \le 10^3\).
- Subtask 3 (30%): No additional constraints.
Examples
Example 1
input
5
3 4 1 5 2
output
1
Example 2
input
3
3 1 2
output
0
Example 3
input
3
1 3 2
output
1
Comments