Business for Badminton
Monty is a little sport-lover boy in his village. Everyone knows Monty for his love towards sports. In winter, Monty prefers to play badminton. But, he founds that playing badminton is little costlier than other games he plays. So he need to arrange a good amount of money to fulfil his wish.
Monty had a jug of exactly 1 litre capacity. He knows that the price of milk varies from day to day in his locality. He decided to start a business with his small jug.
He buys a litre of milk, stores it and sells it in any next day if he finds that profitable for him. After selling milk he plays badminton for two days- the day he sells the milk and the next day. After that, he again tries to find a better profit-making opportunity by buying and selling milk. As you are a great programmer, you will be given with the milk prices of n days. You need to calculate the maximum total profit Monty can make from his business.
Input
In the first line, you will be given an integer N (1 <= N <= 100000) - the number of days.
Followed by N non-negative 32-bit signed integers in the second line.
The i-th integer represents the price of milk in i-th day in that locality.
Output
You have to answer a single number- the maximum profit Monty can make over the N days.
Sample
| Input | Output |
|---|---|
5 1 2 3 0 2 | 3 |
In the sample Monty can maximize his profit by this following strategy:
Day1: buy, Day2: sell, Day3: play badminton, Day4:buy, Day5: sell
Note: No matter what happens, he always plays badminton in the next day he sells milk
