Daydreaming Stockbroker

Interview

Time limit1sMemory limit512 MB

Summary

Given daily stock prices and a 100000 share cap, find the maximum money starting from $100 when whole shares can be bought and sold.

Level: Medium6 of 10
Topics: Greedy, Simulation
Solved: No attempts yet

Problem

Gina Reed, the famous stockbroker, is having a slow day at work, and between rounds of solitaire she is daydreaming. Telling the future is hard. But imagine going back in time and using your knowledge of stock price history to maximize your profit.

Gina starts to wonder: if she went back a few days with a mere $100 in her pocket, how much could she make by buying and selling stock in Rollercoaster Inc. (the most volatile stock in existence) at the right moments? Would it be enough to retire comfortably in a mansion on Tenerife?

Gina cannot buy fractional shares, she buys whole shares only. Rollercoaster Inc. has 100000 shares in total, so Gina can never hold more than 100000 shares at once. In her daydream the world is simple: buying and selling costs no fees, the stock price changes only once per day, and her trading does not move the price.

Input

The first line contains an integer $d$ ( $1 \le d \le 365$ ), the number of days Gina goes back in time in her daydream. Each of the next $d$ lines contains an integer $p_i$ ( $1 \le p_i \le 500$ ), the price at which Gina can buy or sell one share of Rollercoaster Inc. on day $i$ . The days are given from oldest to newest.

Output

Print the largest amount of money Gina can hold once trading on the last day is done. Shares are not money, so any shares she still holds are sold on the last day. The answer can exceed $2^{32}$ .

Examples4

Example 1
Input
```
6
100
200
100
150
125
300
```
Expected output
```
650
```
Example 2
Input
```
1
100
```
Expected output
```
100
```
Example 3
Input
```
5
500
400
300
200
1
```
Expected output
```
100
```
Example 4
Input
```
5
1
2
3
4
5
```
Expected output
```
500
```