Photo
by liz west on flickr, cc by
Gina Reed, the famous stockbroker, is having a slow day
at work, and between rounds of solitaire she is daydreaming.
Foretelling the future is hard, but imagine if you could just
go back in time and use your knowledge of stock price history
in order to maximize your profits!
Now Gina starts to wonder: if she were to go back in time a
few days and bring a measly with her, how much money could she make by just
buying and selling stock in Rollercoaster Inc. (the most
volatile stock in existence) at the right times? Would she earn
enough to retire comfortably in a mansion on Tenerife?
Note that Gina can not buy fractional shares, she must buy
whole shares in Rollercoaster Inc. The total number of shares
in Rollercoaster Inc. is , so Gina can not own more
than shares at
any time. In Gina’s daydream, the world is nice and simple:
there are no fees for buying and selling stocks, stock prices
change only once per day, and her trading does not influence
the valuation of the stock.
Input
The first line of input contains an integer (), the number of days that Gina goes back
in time in her daydream. Then follow lines, the ’th of which contains an integer
() giving the price
at which Gina can buy or sell stock in Rollercoaster
Inc. on day . Days
are ordered from oldest to newest.
Output
Output the maximum possible amount of money Gina can have on
the last day. Note that the answer may exceed .
Sample Input 1 |
Sample Output 1 |
6
100
200
100
150
125
300
|
650
|