Terrace Hill

Time limit1sMemory limit1024 MB

Summary

Given a row of terrace heights, choose a set of non-crossing bridges between equal-height terraces that see each other over lower ground, maximizing total bridge length.

Level: Medium7 of 10
Topics: Stack, Greedy, Dynamic programming, Array
Solved: No attempts yet

Problem

All explored mountain terraces in Girotti hills in Charitum Montes on the southern Martian hemisphere share 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. The unusual configuration of the terraces makes a daring engineering project possible, one that will connect some terraces with bridges.

Because the surrounding region is relatively geologically unstable, the surfaces of any two terraces connected by a bridge must be at the same height. A bridge between two terraces can obviously be built only when the height of every terrace between the two is less than the height of the two terraces to be connected.

The project engineers want to know the maximum total length of all bridges that can be built. To simplify the preliminary calculations, the following assumptions are made. The distance between two neighbouring terraces is negligibly small, and it is taken to be zero in all cases. The width of a terrace is taken to be one length unit.

Input

The first line contains an integer N (1 ≤ N ≤ 3 · 105), the number of terraces. The second line contains N integers a1, a2, . . . , aN (1 ≤ ai ≤ 106), where ai is the height of the i-th terrace. The heights are given in the order of the terraces on the (hypothetical) line.

Output

Print one integer: the maximum possible total length of all bridges.

Examples3

Example 1
Input
```
5
1 2 3 3 1
```
Expected output
```
0
```
Example 2
Input
```
6
5 5 5 3 2 3
```
Expected output
```
1
```
Example 3
Input
```
6
2 3 2 1 2 3
```
Expected output
```
4
```