Problem E
Terrace Hill
All explored mountain terraces in Girotti hills in Charitum Montes on the southern Martian hemisphere have a peculiar feature – their sizes are approximately equal, and they all lie on a hypothetical straight line.
The flat surface of the terraces is ideal for future housing development. Unusual configuration of the terraces allows for a daring engineering project which will connect some terraces by bridges.
Due to relative geological instability in the surrounding region, the surface of any two terraces connected by a bridge has to be in the same height. Obviously, a bridge between two terraces can be built only when the height of all terraces between the given two is less than the height of the two terraces to be connected.
The engineers of the project want to know the maximum total length of all bridges that can be built. To simplify the introductory calculations, the following assumptions are made. The distance between two neighbour terraces is negligibly small, it is considered to be zero in all cases. The width of a terrace is considered to be one length unit.
Input
The first line contains an integer $N$ ($1 \le N \le 3 \cdot 10^5$) the number of the terraces.
The second line contains $N$ integers $a_1, a_2, \dots , a_ N$ ($1 \le ai \le 10^6$) where $a_ i$ is the height of $i$’th terrace. The heights are given in the order of terraces on the (hypothetical) line.
Output
Print one integer – the maximum possible total length of all bridges.
| Sample Input 1 | Sample Output 1 |
|---|---|
5 1 2 3 3 1 |
0 |
| Sample Input 2 | Sample Output 2 |
|---|---|
6 5 5 5 3 2 3 |
1 |
| Sample Input 3 | Sample Output 3 |
|---|---|
6 2 3 2 1 2 3 |
4 |