Work in Mines
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.
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
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
Sample Output 1
Sample Input 2
Sample Output 2
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