Score: 400 points
To become a millionaire, M-kun has decided to make money by trading in the next N days. Currently, he has 1000 yen and no stocks - only one kind of stock is issued in the country where he lives.
He is famous across the country for his ability to foresee the future. He already knows that the price of one stock in the next N days will be as follows:
In the i-th day, M-kun can make the following trade any number of times (possibly zero), within the amount of money and stocks that he has at the time.
What is the maximum possible amount of money that M-kun can have in the end by trading optimally?
Input is given from Standard Input in the following format:
N A_1 A_2 \cdots A_N
Print the maximum possible amount of money that M-kun can have in the end, as an integer.
7 100 130 130 130 115 115 150
1685
In this sample input, M-kun has seven days of trading. One way to have 1685 yen in the end is as follows:
There is no way to have 1686 yen or more in the end, so the answer is 1685.
6 200 180 160 140 120 100
1000
In this sample input, it is optimal to do nothing throughout the six days, after which we will have 1000 yen.
2 157 193
1216
In this sample input, it is optimal to buy 6 stocks in Day 1 and sell them in Day 2, after which we will have 1216 yen.