Problem Description

M-kun aims to become a millionaire and plans to make money through investment over the next $N$ days. Currently, he has $1000 in cash and no stocks. The stocks issued in the country he lives in are of only one type.

He is a nationally renowned clairvoyant and already knows the stock prices for the next $N$ days as follows:

• The stock price on day 1 is $A_1$ yen, on day 2 is $A_2$ yen, ..., and on day $N$ is $A_N$ yen.

On day $i$, M-kun can perform the following transactions as many times as he wants within the limits of his current cash and stocks. It is also acceptable to have days with no transactions.

• Stock purchase: Pay $A_i$ yen to receive 1 stock.
• Stock sale: Sell 1 stock to receive $A_i$ yen.

When M-kun trades optimally, what is the maximum amount of cash he can have at the end?

Input Format

The input is given from the standard input in the following format:

$N$ $A_1$ $A_2$ $\cdots$ $A_N$

Output Format

Output the maximum possible amount of cash M-kun can have at the end as an integer.

Sample Input and Output

Sample Input #1

7
100 130 130 130 115 115 150

Sample Output #1

1685

Sample Input #2

6
200 180 160 140 120 100

Sample Output #2

1000

Sample Input #3

2
157 193

Sample Output #3

1216

Notes/Hints

Constraints

• $2 \leq N \leq 80$
• $100 \leq A_i \leq 200$
• All inputs are integers.

Sample Explanation 1

In this example, M-kun will trade stocks over 7 days. For instance, he can maximize his final cash to $1685$ yen by following this method:
- Initially, M-kun has $1000$ yen and no stocks.
- Day 1: Purchase 10 stocks by paying $1000$ yen, leaving him with $0$ yen.
- Day 2: Sell 7 stocks to receive $910$ yen, leaving him with $910$ yen.
- Day 3: Sell 3 stocks to receive $390$ yen, leaving him with $1300$ yen.
- Day 4: Do nothing.
- Day 5: Purchase 1 stock by paying $115$ yen, leaving him with $1185$ yen.
- Day 6: Purchase 10 stocks by paying $1150$ yen, leaving him with $35$ yen.
- Day 7: Sell 11 stocks to receive $1650$ yen, leaving him with $1685$ yen.
Since it's impossible to have more than $1686$ yen by any trading method, the answer is $1685$.

Sample Explanation 2

In this example, the optimal strategy is to do nothing over the 6 days. This way, M-kun's final cash will be $1000$ yen.

Sample Explanation 3

In this example, the optimal strategy is to purchase 6 stocks on day 1 and sell them all on day 2, resulting in a final cash of $1216$ yen.

见题面 Input 部分

见题面 Output 部分