Interesting Mountains


Submit solution

Points: 1
Time limit: 2.0s
Memory limit: 1000M

Author:
Problem type
Allowed languages
Assembly, C, C++, Java, Pascal, Perl, Python, Text

On your holiday trip to the mountains, you are amazed by the high quality of your Flashy Yellow Panorama Camera. After shooting a couple of nice photos during your hike, you decide to send the nicest one to your best friend. Sure enough, they immediately reply that they see all kinds of fancy patterns -- but they are not talking about the beautiful snow-capped mountains: they have a more abstract view of the photo...

Since the heights of the \(n\) mountains in the panorama photo are unique, you can view these heights as a permutation of all numbers between \(1\) and \(n\) (inclusive). Your friend thinks that a formation of three (not necessarily consecutive) mountains is interesting, when the first mountain is higher than the third mountain, and the third mountain is higher than the second mountain. In other words, three mountains with indices \(i, j,\) and \(k \ (1 \le i < j < k \le n)\) and respective heights \(h_i, h_j,\) and \(h_k\) are interesting, if and only if \(h_i > h_k > h_j\). How many interesting formations can you find in a given panorama photo?

As an example, consider the first sample input: only the tuples with indices \((1, 3, 5)\) and \((2, 3, 5)\) are interesting formations.

Input

The input consists of:

  • One line with an integer \(n \ (3 \le n \le 3 \cdot 10^5)\), the number of mountains in the photo.
  • One line with \(n\) integers \(h_1, \ldots, h_n \ (1 \le h_i \le n\) for each \(i)\), the heights of the mountains in the photo. It is guaranteed all values of \(h_i\) are unique.

Output

Output the number of interesting formations in the panorama photo.

Examples

Sample 1

input

5
3 4 1 5 2

output

2
Sample 2

input

3
3 1 2

output

1
Sample 3

input

3
2 1 3

output

0
Sample 4

input

11
5 9 10 11 1 2 3 4 6 7 8

output

69

Comments

There are no comments at the moment.