Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Business for Badminton

By piyush_15026 · Limits 500ms, 512 MB

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

InputOutput
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

    Discussion

    Statistics


    38% Solution Ratio

    Tawsifiit48Earliest, 1M ago

    RamprosadGFastest, 0.0s

    steinumLightest, 918 kB

    MursaleenShortest, 304B

    Submit

    Login to submit