Indian National Olympiad in Informatics

Related:

Online Programming Contest, 15-16 September 2007

IARCS home > OLYMPIAD

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⁸.

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