Kanhaiya Agarwal got placed in Flipkart. So he gifted me a land which can be used for mining.

I divided the land into sections called plots, linearly. Each plot has its own size. Minimum 1 worker is to be allotted to each plot. If two plots are adjacent to each other, then the one with greater size has to be allotted more number of workers. I want to minimize the total number of workers allotted. Help me out.

Input

The first line of the input is an integer N, the number of plots. Each of the following N lines contains an integer indicating the size of each plot.

The order of given plots is not to be changed

Ouput

Output a single line containing the minimum number of workers to be put to work.

Value of N and Size of Plots is less than 10^5

Sample Input 1

``` 5 1 5 6 3 4 ```

Sample Output 1

``` 9 ```

Sample Input 2

``` 6 1 2 3 4 5 5 ```

Sample Output 2

``` 16 ```

For the 2nd Test Case:
1 is allotted 1
2 is allotted 2
3 is allotted 3
4 is allotted 4
5 is allotted 5
5 is allotted 1

Rounak Tibrewal

Languages: C,C++,Java

Time Limit: 1 Second(s)
Score: 100 Point(s)
Input File Limit: 50000 Bytes

Mode Judge

RankNameScore
1xyz0
2Ams0
3TIP0
4team420
5xyzz0
6asdasdasd0
7abcd0
8khankhan0
9Gabriel0
10gigel0