1. Pepcoder is wishing to give offerings to all the temples along a mountain range.
2. The temples are located in a row at different heights.
3. You have to find the minimum number of offerings such that these conditions are fulfilled -
-> If two adjacent temples are at different heights, then the temple which is situated at greater height should receive more offerings.
-> If two adjacent temples are at the same height, then their offerings relative to each other does not matter. Input Format
A number N, which represents number of temples. An array of positive integers, where every element of array represents height of temple from ground level.
Output Format
Check the sample output and question video.
Constraints
1 <= N <= 10^8 1 <= arr[i] <= 10^3
Example
Input
6 1 3 2 5 2 1
Output
10