Yegor loves Moscow very much and often goes for a walk to admire its views.
Moscow in Egor's view is a long straight highway, along which there are n towers, numbered in their order from 1 to n. All towers have different heights, which are expressed as integers from 1 to n . The height of tower i is h
i .
However, Egor does not like increasing sequences. He is disappointed with triplets of towers, such that as their indices increase, their values also increase. More formally, the triple of towers numbered i , j and k disappoints Egor if i < j < k and h
i < h
j < h k .
Egor knows the heights of all the towers in Moscow in advance and wants to know if he will be very disappointed on a walk. Help him determine how many tower triplets he will be disappointed with.
Input
The first line of the input contains a single number n — number of towers in Moscow ( 1 ≤ n ≤ 8000 ).
The second line of the input contains n distinct natural numbers, the i -th of them h i — height of i -th tower ( 1 ≤ h
i ≤ n ).
Imprint
Print one number — the number of triples of towers that will disappoint Egor.
Note that the response may not fit in the standard 32-bit data type. It is necessary to use a 64-bit type, in pascal it is called « int64 ", in C++ " long long ", in Java " long».
Examples
| # |
Input |
Output |
| 1 |
5
1 3 4 2 5
| 5 |
| 2 |
3
3 1 2
| 0 |