Mountains

Interview

Time limit2sMemory limit256 MB

Summary

Count triples x < y < z where the middle mountain y is strictly taller than both mountain x and mountain z.

Level: Medium5 of 10
Topics: Array, Combinatorics, Prefix sum, Sorting
Solved: No attempts yet

Problem

Pengu the Penguin lives in Antarctica with his penguin friends. They are flightless birds, but they want to feel the joy of soaring through the air. Pengu decides to grant their wish with technology: gliders.

Luckily for Pengu, there are n mountains in the Transantarctic Mountain Range. The mountains are labelled 1 to n and are arranged in a row from left to right. The ith mountain has height Hi.

Pengu decides to pick three mountains x, y and z. He plans to build a base station on mountain y and receiving stations on mountains x and z. Penguins will glide from mountain y to either mountain x or z. To accommodate more penguins while avoiding midair collisions, mountain x is to the left of mountain y and mountain z is to the right of mountain y. Furthermore, mountains x and z must be strictly shorter than mountain y. Pengu is very meticulous and wants to consider all possible choices. Find the number of possible choices for (x, y, z) such that 1 ≤ x < y < z ≤ n, Hx < Hy and Hy > Hz.

Input

Your program must read from standard input. The first line contains an integer n, the number of mountains. The second line contains n integers, where the ith integer represents the height of the ith mountain Hi.

Output

Your program must print to standard output.

The output should contain a single integer on a single line, the total number of possible choices for (x, y, z).

Constraints

3 ≤ n ≤ 3 × 105
0 ≤ Hi ≤ 1018

Examples2

Example 1
Input
```
5
0 1 1 0 1
```
Expected output
```
2
```
Example 2
Input
```
6
500 20 900 0 900 70
```
Expected output
```
7
```