### Indian National Olympiad in Informatics

### Online Programming Contest, 15-16 September 2007

### Basic Division

Problem 1: Thambi the Gold Speculator, *(K Narayan Kumar, CMI)*

Thambi read in the paper that the world economy was going through a
volatile phase, one indication of which was the wild fluctuation in
the price of gold. He thought that speculating on gold would be an
excellent way to make money quickly. To limit his losses while he
sharpened his skills, he decided to buy or sell only 1 gram each day,
never holding on to more than 1 gram in stock. He believed that he
could make a killing by buying a gram of gold whenever the price was
low and selling it whenever the price was high.

Before entering the gold market, Thambi decided to examine to examine
the variation in the price of gold over the last few days and determine
the maximum profit he could have made.

Suppose, the price of 1 gram of gold varied over a period of 10 days
as follows:

Day 1 2 3 4 5 6 7 8 9 10
Price 113 71 102 93 130 145 101 153 122 101

His best strategy here is to buy on day 2, sell on day 3, buy on
day 4, sell on day 6, buy on day 7, sell on day 8 for a total profit
of (102-71) + (145-93) + (153-101) = 135.

You will be given the price of 1 gram of gold over a sequence of N
days. Your task is to determine the maximum profit that Thambi can
make by choosing appropriate days to buy and sell gold. Remember that
he never holds more than 1 gram in stock and he always buys and sells
at most 1 gram each day.

Input format

The first line of input is a single integer *N*, the number
of days. The second line of input consists of *N* integers,
representing the price of 1 gram of gold for days 1 to *N*.

Output format

Your output should be a single integer, the maximum profit that
Thambi can make by judiciously buying and selling gold over *N*
days.

Test data

You may assume that *N* ≤ 10^{8}.

Example

Here is the sample input and output corresponding to the
example discussed above.

Sample input

10
113 71 102 93 130 145 101 153 122 101

Sample output

135