Problem:
 Score: 400 points    Problem Statement  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:   A_1 yen on the 1 -st day, A_2 yen on the 2 -nd day, ..., A_N yen on the N -th day.   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 .   Buy stock: Pay A_i yen and receive one stock.  Sell stock: Sell one stock for A_i yen.   What is the maximum possible amount of money that M-kun can have in the end by trading optimally?      Constraints   2 \leq N \leq 80  100 \leq A_i \leq 200  All values in input are integers.         Input  Input is given from Standard Input in the following format:  N  A_1  A_2  \cdots  A_N       Output  Print the maximum possible amount of money that M-kun can have in the end, as an integer.        Sample Input 1 7
100 130 130 130 115 115 150      Sample Output 1 1685  In this sample input, M-kun has seven days of trading. One way to have 1685 yen in the end is as follows:   Initially, he has 1000 yen and no stocks.  Day 1 : Buy 10 stocks for 1000 yen. Now he has 0 yen.  Day 2 : Sell 7 stocks for 910 yen. Now he has 910 yen.  Day 3 : Sell 3 stocks for 390 yen. Now he has 1300 yen.  Day 4 : Do nothing.  Day 5 : Buy 1 stock for 115 yen. Now he has 1185 yen.  Day 6 : Buy 10 stocks for 1150 yen. Now he has 35 yen.  Day 7 : Sell 11 stocks for 1650 yen. Now he has 1685 yen.   There is no way to have 1686 yen or more in the end, so the answer is 1685 .       Sample Input 2 6
200 180 160 140 120 100      Sample Output 2 1000  In this sample input, it is optimal to do nothing throughout the six days, after which we will have 1000 yen.       Sample Input 3 2
157 193      Sample Output 3 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.

Solution (Python):
N=int(input())
A=list(map(int,input().split()))

dp=[0]*(N)
dp[0]=1000
for i in range(1,N):
    for j in range(i+1):
        stock=dp[i-j]//A[i-j]
        money=stock*A[i]+dp[i-j]-stock*A[i-j]
        dp[i]=max(dp[i],dp[i-j],money)
print(dp[N-1])

Solution (Python):
n = int(input())
a_list = list(map(int, input().split()))

money = 1000
num = 0

for i in range(len(a_list)-1):
    if a_list[i] <= a_list[i+1]:
        num += money // a_list[i]
        money -= num * a_list[i]

        money += num * a_list[i+1]
        num = 0

print(money)

Solution (Python):
n, *a = map(int, open(0).read().split())
money = 1000
stock = 0
for i in range(n-1):
    if a[i] < a[i+1]:
        stock = money // a[i]
        money += (a[i+1] - a[i]) * stock
print(money)

Solution (Python):
n, *a = map(int, open(0).read().split())
max_a = max(a)
money = 1000
stock = 0
for i in range(n-1):
    if a[i] < a[i+1]:
        stock = money // a[i]
        money += (a[i+1] - a[i]) * stock
print(money)

Solution (Python):
n = int(input())
a = list(map(int, input().split()))





money = 1000
stock = 0
for i in range(n):
    if i == n-1 or a[i] > a[i+1]:
        money += stock * a[i]
        stock = 0
    elif money > a[i]:
        stock = money // a[i]
        money = money % a[i]

print(money)

Solution (Python):
import sys
input = sys.stdin.readline


def main():
    n = int(input())
    A = list(map(int, input().split()))
    flags = [0] * n
    up = False
    prev = 1000
    for i, a in enumerate(A):
        if up:
            if a < prev:
                flags[i-1] = -1
                up = False
        else:
            if a > prev:
                flags[i-1] = 1
                up = True
        prev = a

    money = 1000
    kabu = 0
    for flag, a in zip(flags, A):
        if flag == 1:
            kabu += money // a
            money %= a

        elif flag == -1:
            money += kabu * a
            kabu = 0

    if kabu:
        money += A[-1] * kabu

    print(money)


if __name__ == "__main__":
    main()

Solution (Python):
N = int(input())
A = list(map(int, input().split()))

fm = 1000
nm = (0, 0)

for a in A:
	nfm = max(fm, nm[0] * a + nm[1])
	nnm = max(nm, (fm//a, fm - fm//a*a))

	fm, nm = nfm, nnm

print(fm)

Solution (Python):


import copy
import random
import bisect 
import fractions 
import math
import sys
import collections
from decimal import Decimal 

mod = 10**9+7
sys.setrecursionlimit(mod) 

d = collections.deque()
def LI(): return list(map(int, sys.stdin.readline().split()))

















N = int(input())
A = LI()

cash = 1000
stocks = 0
for i in range(N - 1): 
    if A[i] < A[i + 1]: 
        buy_stocks = cash // A[i]
        stocks += buy_stocks
        cash -= buy_stocks * A[i]
    else: 
        cash += stocks * A[i]
        stocks = 0
cash += stocks * A[-1] 
print(cash)

Solution (Python):
def main():
  n = int(input())
  a = list(map(int, input().split()))
  a.append(-1)
  num_kabu = 0
  money = 1000
  for i in range(0, n):
    if a[i+1] >= a[i]:
      num_kabu += money//a[i]
      money %= a[i]
    if a[i+1] <a[i]:
      money += num_kabu*a[i]
      num_kabu = 0
  print(money)
  
if __name__ =="__main__":
  main()

Solution (Python):
import sys
import itertools

import time
import math
import heapq
from collections import defaultdict
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines



N = int(input())
A = list(map(int, input().split()))

cur = 1000
left = 0
right = 1
while left < N:
    while right < N and A[right] > A[right - 1]:
        right += 1
    if right - left > 1:
        stocks = cur // A[left]
        cur = cur % A[left]
        cur += A[right - 1] * stocks
    left = right
    right = left + 1
print(cur)

Solution (Python):
n = int(input())
a = list(map(int, input().split()))

tmp = 1000
for i in range(n-1):
    s = 0
    if a[i] < a[i+1]:
        s = tmp//a[i]
        tmp += (a[i+1]-a[i])*s
print(tmp)

Solution (Python):
N = int(input())
A = list(map(int,input().split()))

minval = 0
ans = 1000

for i in range(1, N):
  if A[i] > A[minval]:
    pstock = ans // A[minval]
    ans = ans%A[minval] + A[i]*pstock
  minval = i

print(ans)

Solution (Python):
import time
N = int(input())
A = list(map(int, input().split()))

left = 0
right = left + 1
money = 1000

while left < N - 1:

    if A[left] >= A[left+1]:
        left += 1
        right = left
        continue

    if right <= N-2:
        if A[right] <= A[right+1]:
            right += 1
            continue

    money += (money//A[left]) * (A[right]-A[left])
    left = right

print(money)

Solution (Python):
n = int(input())
data = list(map(int, input().split()))

ans = 0
money = 1000

for idx in range(n-1):
    today = data[idx]
    tmr = data[idx+1]
    if tmr > today:
        money += (tmr-today) * (money//today)

print(money)

Solution (Python):
N=int(input())
A=list(map(int,input().split()))
money=1000
buy=0
for i in range(N-1):
    if A[i]<=A[i+1]:
        buy=money//A[i]
        money=A[i+1]*buy+money%A[i]
print(money)

Solution (Python):
INF = 300

n = int(input())
a = [INF] + list(map(int, input().split())) + [-INF]

money = 1000
stock = 0
for e1, e2 in zip(a, a[1:]):
    if e1 < e2:
        buy = money // e1
        money -= buy * e1
        stock += buy
    else:
        money += stock * e1
        stock = 0

print(money)

Solution (Python):
N = int(input())
A = list(map(int,input().split()))
M = 1000
S = 0
for i in range(N-1):
  M+=S*A[i]
  S = 0
  if A[i+1]>=A[i]:
    tmp=M//A[i]
    M -= tmp*A[i]
    S+=tmp
M+=S*A[-1]
S = 0
print(M)

Solution (Python):
N = int(input())

A = list(map(int, input().split()))

dp = [0] * N
dp[0] = 1000

for i in range(1, N):
    dp[i] = dp[i - 1]
    t = dp[i - 1] + (A[i] - A[i - 1]) * (dp[i - 1] // A[i - 1])
    dp[i] = max(dp[i], t)

print(dp[-1])

Solution (Python):
n = int(input())
a_i = list(map(int, input().split()))
preval = a_i[0]
cnt = 0
money = 1000
for x in range(1,n):
    val = a_i[x]
    if cnt == 0 and preval < val:
        cnt = money // preval
        money = money % preval
    elif cnt != 0 and preval > val:
        money += cnt * preval
        cnt = 0
    preval = val
if cnt != 0:
    money += cnt * val
print(money)

Solution (Python):
n = int(input())
a = list(map(int, input().split()))
money = 1000
stock = 0
for i in range(n-1):
    if a[i+1] > a[i]:
        stock = money // a[i]
        money += (a[i+1] - a[i]) * stock
print(money)

Solution (Python):
N = int(input())
An = list(map(int, input().split()))
money = 1000
stock = 0
for i in range(N-1):
    if An[i+1] > An[i]:
        stock = money // An[i]
        money += (An[i+1] - An[i]) * stock
print(money)

Solution (Python):
N = int(input())
A = list(map(int, input().split()))
ans = 1000
for i in range(N - 1):
    a = A[i]
    if a < A[i + 1]:
        units = ans // a
        ans = (ans - units * a) + units * A[i + 1]
    

print(ans)

Solution (Python):
n = int(input())
a = list(map(int, input().split()))

d = {}
d[0] = 1000

for i in range(n):
    e = d.copy()
    for stock, money in e.items():
        
        d[0] = max(d[0], money + stock * a[i])
        
        k = money // a[i]
        stock += k
        money -= k * a[i]
        d[stock] = max(d.get(stock, 0), money)

print(d[0])

Solution (Python):
def find(A):
    increase = []
    for i in range(len(A)-1):
        if A[i] <= A[i+1]:
            increase += [1]
        else:
            increase += [0]
    increase += [0]
    
    val = 1000
    hold = 0
    for i in range(len(increase)):
        if i==0:
            if increase[i] == 1:
                hold = val//A[i]
                val -= A[i]*hold
        else:
            if increase[i] == 1:
                if increase[i-1] == 0:
                    hold = val//A[i]
                    val -= A[i]*hold 
            else:
                if increase[i-1] == 1:
                    val += A[i]*hold
                    hold = 0
    return val
N = input()
A = list(map(int,input().strip().split()))
print(find(A))

Solution (Python):
N = int(input())
A = list(map(int, input().split()))
money = 1000
cnt = 0
if A[0] < A[1]:
    cnt += 1000 // A[0]
    money = money % A[0]
for i in range(1, N-1):
    if A[i] <= A[i - 1] and A[i] < A[i + 1]:
        cnt += money // A[i]
        money = money % A[i]
    elif A[i] >= A[i-1] and A[i] > A[i + 1]:
        money += cnt * A[i]
        cnt = 0
if cnt != 0:
    money += cnt * A[N - 1]
    cnt = 0
print(money)

Solution (Python):
import os
import sys
import math
import heapq
from decimal import *
from io import BytesIO, IOBase
from collections import defaultdict, deque

def r():
    return int(input())
def rm():
    return map(int,input().split())
def rl():
    return list(map(int,input().split()))

n=r()
a=rl()
money=1000
s=0

for i in range(n):
    if i==n-1:
        money+=s*a[i]
    else:
        if a[i]<=a[i+1]:
            money+=s*a[i]
            s=money//a[i]
            money%=a[i]
        else:
            money+=s*a[i]
            s=0
print(money)

Solution (Python):
n = int(input())
A = list(map(int, input().split()))

money = 1000
kabu = 0
memo = []

buy = True

for i in range(n-1):
    if buy:
        if A[i] < A[i+1]:
            kabu = money //A[i]
            money %= A[i]
            buy = False
    else:
        if A[i] > A[i+1]:
            money += kabu * A[i]
            kabu = 0
            buy = True

if kabu:
    money += kabu * A[n-1]

print(money)

Solution (Python):
N = int(input())
a = list(map(int,input().split()))
S = 1000
K = 0
b = 1
last = 0
			
for i in range(N):
	if i != N-1:
		if a[i]<=a[i+1]:
			S += a[i]*K
			K = S // a[i]
			S -= K*a[i]

		else:
			S += a[i]*K
			K = 0
	else:

		S += a[i]*K
print(S)

Solution (Python):
N = int(input())

A = list(map(int, input().split()))

money = 1000

for i in range(N-1):
    t = money + (A[i + 1] - A[i]) * (money // A[i])
    money = max(money, t)

print(money)

Solution (Python):
n= int(input())
arr = [int(x) for x in input().strip().split()]


def Greedy(arr):
    
    curr = 1000
    for i in range(len(arr)-1):
        if arr[i+1]>arr[i]:
            stocks = curr // arr[i]
            curr += (arr[i+1] - arr[i])*stocks
    return curr

print(Greedy(arr))

Solution (Python):
n= int(input())
arr = [int(x) for x in input().strip().split()]


def Greedy(arr):
    
    curr = 1000
    for i in range(len(arr)-1):
        if arr[i+1]>arr[i]:
            stocks = curr // arr[i]
            curr += (arr[i+1] - arr[i])*stocks
    return curr

print(Greedy(arr))

Solution (Python):
n= int(input())
arr = [int(x) for x in input().strip().split()]


def Greedy(arr):
    
    curr = 1000
    for i in range(len(arr)-1):
        if arr[i+1]>arr[i]:
            stocks = curr // arr[i]
            curr += (arr[i+1] - arr[i])*stocks
    return curr

print(Greedy(arr))

Solution (Python):
N = int(input())
A = [int(i) for i in input().split()]

W = [0] * N

for i in range(1, N):
    W[i] = A[i] - A[i - 1]
B = [0]
for w in W:
    if not w == 0:
        B.append(w)
l = len(B)
money = 1000
kabu = 0
value = A[0]
for i in range(l):
    value += B[i]
    if (i == l - 1) or (B[i] > 0 and B[i + 1] < 0):
        money += kabu * value
        kabu = 0
    elif (i == 0 and B[i + 1] > 0) or (B[i] < 0 and B[i + 1] > 0):
        n = money // value
        money -= n * value
        kabu += n

print(money)

Solution (Python):
n = int(input())
a = list(map(int,input().split()))
money = 1000
for i in range(n-1):
    stock  = 0 if a[i] > a[i+1] else money // a[i]
    money += (a[i+1]-a[i])*stock
print(money)

Solution (Python):
N = int(input())
A = list(map(int, input().split()))

money = 1000;stack=0

for i in range(N-1):
    if A[i]<A[i+1]:
        stack+=money//A[i]
        money %= A[i]
    elif A[i]>A[i+1]:
        money += stack*A[i]
        stack=0

money += stack*A[N-1]
stack=0

print(money)

Solution (Python):
N = int(input())
A = list(map(int,input().split()))

money = 1000
stocks = 0

for n in range(N-1):
  if A[n] < A[n+1]:
    stocks += money//A[n]
    money = money%A[n]
  elif A[n] > A[n+1]:
    money += stocks*A[n]
    stocks = 0
money += stocks * A[-1]
print(money)

Solution (Python):
N = int(input())
A = list(map(int,input().split()))
money = 1000
stock = 0
for i in range(N-1):
    if A[i] > A[i+1]:
        money += A[i]*stock
        stock = 0
    elif A[i] < A[i+1]:
        stock += money//A[i]
        money = money%A[i]
money += stock*A[-1]
print(money)

Solution (Python):
n = int(input())
a = list(map(int,input().split()))

dp = [0 for _ in range(n)]
dp[0] = 1000

kabu = [0 for _ in range(n)]

for i in range(1,n):
    kabu[i-1] = dp[i-1] // a[i-1] 
    oturi = dp[i-1] - kabu[i-1]*a[i-1]
    dp[i] = max(kabu[i-1]*a[i]+oturi, dp[i-1])

print(dp[-1])

Solution (Python):
n = int(input())
a = list(map(int, input().split()))
p = 1000
k = 0
for i in range(n-1):
    if k>0 and a[i]>a[i+1]:
        p += k*a[i]
        k = 0
    elif k==0 and a[i]<a[i+1]:
        k = p//a[i]
        p %= a[i]
if k>0:
    p += k*a[-1]
print(p)

Solution (Python):
N = int(input())
A = list(map(int, input().split()))

kane=1000
kabu=0
for i in range(N-1):
    
    
    if A[i]<A[i+1]:
        kane=kabu*A[i]+kane
        kabu=kane//A[i]
        kane=kane-kabu*A[i]
    else:
        kane=kabu*A[i]+kane
        kabu=0
        
print(kane+kabu*A[N-1])

Solution (Python):
n = int(input())
a = list(map(int,input().split()))
b = [0]*n
for i in range(n-1):
    if(a[i] < a[i+1]):
        
        b[i] = 1
        
        
    if(a[i] > a[i+1]):
        
        b[i] = -1
        
        
    
        
    
     
      
b[-1] = -1

h = [1000,0]
for i in range(n):
    if(b[i] == 1):
        h[1] += h[0]//a[i]
        h[0] %= a[i]
    elif(b[i] == -1):
        h[0] += h[1]*a[i]
        h[1] *= 0
    
print(h[0])

Solution (Python):
N = int(input())
A = list(map(int, input().split()))

dp = [0]*(N)
dp[0] = 1000

for i in range(1,N):
    dp[i] = dp[i-1]
    for j in range(i):
        dp[i] = max(dp[i], (dp[j]//A[j])*A[i]+dp[j]%A[j])
ans = 0
for i in range(N):
    ans = max(ans, dp[i])
print(ans)

Solution (Python):
n = int(input())
a = list(map(int, input().split()))

money = 1000
mount = 0

f = -1
pre = a[0]
for i in range(1, len(a)):
    if f < 0:
        if a[i] <= pre:
            pre = a[i]
            continue
        mount += money // pre
        money %= pre
        f *= -1
    else:
        if a[i] >= pre:
            pre = a[i]
            continue
        money += mount * pre
        mount = 0
        f *= -1

    pre = a[i]

money += mount * a[-1]
print(money)

Solution (Python):


from pprint import pprint
from collections import deque, defaultdict
import itertools
import math
import sys

sys.setrecursionlimit(10 ** 6)
INF = float('inf')


N = int(input())
A = list(map(int, input().split()))




dp = [0] * (N+1)
dp[0] = 1000

for i in range(1, N+1):
    
    max_j = 0
    for j in range(1, i):
        
        q, r = divmod(dp[j-1], A[j-1])
        
        max_j = max(max_j, A[i-1] * q + r)
    
    dp[i] = max(dp[i-1], max_j)


print(dp[N])

Solution (Python):
n = int(input())
tmp = input().split(' ')
tmp_map = map(int,tmp)
prices = list(tmp_map)
money = 1000

for i in range(n-1):
  if prices[i] < prices[i+1]:
    stocks = int(money/prices[i])
    money += stocks*(prices[i+1]-prices[i])

print(money)

Solution (Python):
input()
A=list(map(int,input().split()))
M=[0,1000]
for i in range(0,len(A)-1):
    if A[i]>A[i+1]:
        M[1]+=A[i]*M[0]
        M[0]=0
    elif A[i]<A[i+1]:
        M[0]+=int(M[1]/A[i])
        M[1]=M[1]%A[i]
M[1]+=A[i+1]*M[0]
M[0]=0
print(M[1])

Solution (Python):
N = int(input())
A = list(map(int, input().split()))
M = 1000
S = 0
for i in range(N-1):
    if A[i] < A[i+1]:
        S = M // A[i]
        M = M % A[i] + S*A[i+1]
        S = 0
    else:
        pass
print(M)

Solution (Python):
n=int(input())
a = input().split(" ")
lista = [int(n) for n in a]
kane=1000
k=0
for i in range(n-1):
  c=lista[i]
  d=lista[i+1]
  if c<d:
    b=kane//c
    kane-=b*c
    k+=b
  elif c>=d:
    kane+=k*c
    k=0
  if i==n-2:
    kane+=k*lista[n-1]
    k=0
print(kane)

Solution (Python):
import sys
readline = sys.stdin.readline



N = int(readline())
A = list(map(int,readline().split()))

money = 1000
for i in range(N - 1):
  if A[i] < A[i + 1]:
    kabu = money // A[i]
    money %= A[i]
    money += kabu * A[i + 1]
    
print(money)

Solution (Python):
import sys
from collections import deque,defaultdict

I=sys.stdin.readline

def ii():
	return int(I().strip())
def li():
	return list(map(int,I().strip().split()))

def mi():
	return map(int,I().strip().split())


def main():
	n=ii()
	arr=li()
	p=1000
	for i in range(n-1):
		if arr[i]<arr[i+1]:
			buy=p//arr[i]
			p+=(arr[i+1]-arr[i])*buy

	
	print(p)








		


		










		






if __name__ == '__main__':
	main()

Solution (Python):
import sys
from collections import deque,defaultdict

I=sys.stdin.readline

def ii():
	return int(I().strip())
def li():
	return list(map(int,I().strip().split()))

def mi():
	return map(int,I().strip().split())


def main():
	n=ii()
	arr=li()
	p=1000
	for i in range(n-1):
		if arr[i]==arr[i+1]:
			pass
		elif arr[i]<arr[i+1]:
			buy=p//arr[i]
			p+=(arr[i+1]-arr[i])*buy

	
	print(p)








		


		










		






if __name__ == '__main__':
	main()

Solution (Python):
import sys, bisect, math, itertools, string, queue, copy
import numpy as np
import scipy
from collections import Counter,defaultdict,deque
from itertools import permutations, combinations
from heapq import heappop, heappush
from fractions import gcd
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(input())
def inpm(): return map(int,input().split())
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())
def inplm(n): return list(int(input()) for _ in range(n))
def inplL(n): return [list(input()) for _ in range(n)]
def inplT(n): return [tuple(input()) for _ in range(n)]
def inpll(n): return [list(map(int, input().split())) for _ in range(n)]
def inplls(n): return sorted([list(map(int, input().split())) for _ in range(n)])

n = inp()
a = inpl()
sign = [-1]*n

pre = -1
for i in range(1,n):
    if a[i] > a[i - 1]:
        sign[i] = 1
        pre = 1
    elif a[i] < a[i - 1]:
        sign[i] = -1
        pre = -1
    else:
        sign[i] = pre

money = 1000
stock = 0
for i in range(n):
    if sign[i] == 0 or (i != n-1 and sign[i] == sign[i + 1]):
        continue

    if sign[i] == 1:
        
        money += a[i] * stock
        stock = 0
    elif sign[i] == -1:
        flg = False
        if [j for j in sign[i:] if j == 1]:
            flg = True
        
        if flg == True:
            buy =  money // a[i]
            stock += buy
            money -= a[i] * buy
print(money)

Solution (Python):
import copy
def main():
    N = int(input())
    A = [int(a) for a in input().split()]

    money = 1000
    stock = 0
    day = 0

    while day < len(A) - 1:
        if A[day + 1] - A[day] > 0:
            cur = copy.deepcopy(day)
            while day < (len(A) - 1):
                if A[day + 1] - A[day] < 0:
                    break
                else:
                    day += 1

            r, m = divmod(money, A[cur])
            stock += r
            money -= r * A[cur]
            money += stock * A[day]
            stock = 0

        elif A[day + 1] - A[day] < 0:
            cur = copy.deepcopy(day)
            while day < (len(A) - 1):
                if A[day + 1] - A[day] > 0:
                    break
                else:
                    day += 1

            if day < len(A) - 1:
                r, m = divmod(money, A[day])
                stock += r
                money -= r * A[day]

        elif A[day + 1] - A[day] == 0:
            day += 1

    print(money)

if __name__ == "__main__":
    main()

Solution (Python):
'''
自宅用PCでの解答
'''
import math

import itertools
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit


ipt = stdin.readline
setrecursionlimit(10**7)
mod = 10**9+7

def main():
    n = int(ipt())
    a = [int(i) for i in ipt().split()]
    yt = []
    p = 1
    nk = 1000
    kb = 0
    for i,na in enumerate(a[1::]):
        ai = a[i]
        if p:
            if ai < na:
                p = 0
                kb = nk//ai
                nk %= ai
        else:
            if ai > na:
                p = 1
                nk += kb*ai
                kb = 0

    print(nk+kb*a[-1])
    return None

if __name__ == '__main__':
    main()

Solution (Python):
N = int(input())
A = list(map(int, input().split()))

Stock = 0
Money = 1000
 
for i in range(N-1):
    if A[i] < A[i + 1]:

        Stock = Money // A[i]
        Money %= A[i]
        Money += Stock * A[i+1]
print(Money)

Solution (Python):
N = int(input())

A = list(map(int, input().split()))

dp = [0] * N
dp[0] = 1000

for i in range(1, N):
    dp[i] = dp[i - 1]
    for j in range(i):
        kabu = dp[j] // A[j]
        money = dp[j] + (A[i] - A[j]) * kabu
        dp[i] = max(dp[i], money)

print(dp[-1])

Solution (Python):
n = int(input())
a = input().split()

money = 1000
stock = 0
pivot = []
upflag = 0
dnflag = 1

if(int(a[1]) - int(a[0]) > 0): 
    stock = int(money // (int(a[0])))
    money = int(money % (int(a[0])))
    upflag = 1
    dnflag = 0

for i in range(n-2): 
    if(int(a[i+1]) == int(a[i])):
        if((int(a[i+2]) - int(a[i+1]) < 0) and upflag == 1): 
            money = money + stock * (int(a[i+1]))
            stock = 0
            upflag = 1
            dnflag = 0
        elif((int(a[i+2]) - int(a[i+1]) > 0) and dnflag == 1): 
            stock = int(money // (int(a[i+1])))
            money = int(money % (int(a[i+1])))
            upflag = 0
            dnflag = 1

    elif(int(a[i+1]) - int(a[i]) > 0):
        upflag = 1
        if(int(a[i+2]) - int(a[i+1]) < 0): 
            money = money + stock * (int(a[i+1]))
            stock = 0
            upflag = 0

    elif(int(a[i+1]) - int(a[i]) < 0):
        dnflag = 1
        if(int(a[i+2]) - int(a[i+1]) > 0): 
            stock = int(money // (int(a[i+1])))
            money = int(money % (int(a[i+1])))
            dnflag = 0

if(int(a[n-1]) - int(a[n-2]) > 0): 
    money = money + stock * (int(a[n-1]))
elif(int(a[n-1]) - int(a[n-2]) == 0):
    if(upflag == 1):
        money = money + stock * (int(a[n-1]))

print(money)

Solution (Python):
import sys
input = sys.stdin.readline

n=int(input())
L=list(map(int,input().split()))

dp = [1000]*n

for i in range(n):
    dp[i]=max(dp[i-1],dp[i])
    st,rest=divmod(dp[i],L[i])
    for j in range(i+1,n):
        dp[j] = max(dp[j],L[j]*st+rest)
print(dp[-1])

Solution (Python):
N = int(input())
A = list(map(int, input().split()))






dp = [0] * N

dp[0] = 1000 
for i in range(1, N):
  
  for j in range(0, i):
    
    v = int(dp[j] / A[j])
    
    
    
    
    
    w = dp[j] - v*A[j] + v*A[i]
    
    dp[i] = max(dp[i-1], w)
    
print(max(dp))

Solution (Python):
import sys
read = sys.stdin.readline
import time
import math
import itertools as it
def inp():
    return int(input())
def inpl():
    return list(map(int, input().split()))
st = time.perf_counter()


N = inp()
A = inpl()
stk = 0
yen = 1000
for i in range(N):
    if i == 0:
        if A[i] < A[i+1]:
            stk += yen // A[i]
            yen %= A[i]
    elif i == N-1:
        yen += stk * A[i]
    else:
        if A[i-1] <= A[i] and A[i] > A[i+1]:
            yen += A[i]*stk 
            stk = 0
        if A[i-1] >= A[i] and A[i] < A[i+1]:
            stk += yen // A[i]
            yen %= A[i]
print(yen)


ed = time.perf_counter()
print('time:', ed-st, file=sys.stderr)

Solution (Python):
N = int(input())
A = list(map(int, input().split()))

t = [-1] * (N + 1)
t[0] = 1000
for i in range(N):
    k = t[i] // A[i]
    y = t[i] % A[i]
    for j in range(i, N):
        t[j + 1] = max(t[j + 1], k * A[j] + y)
print(t[N])

Solution (Python):

n = int(input())
a = list(map(int, input().split()))
ans = 1000
left = 0
right = 0
while left < n:
    right = left
    while right + 1 < n and a[right] <= a[right + 1]:
        right += 1
    ans = ans // a[left] * a[right] + ans % a[left]
    left = right
    left += 1
print(ans)

Solution (Python):
N = int(input())
A = list(map(int, input().split()))

iStock = 0
iMoney = 1000

for i in range(N-1):
    if A[i] < A[i + 1]:
        
        iStock = iMoney // A[i]
        iMoney %= A[i]
        iMoney += iStock * A[i+1]
print(iMoney)

Solution (Python):
N = int(input())
A = list(map(int, input().split()))

iStock = 0
iMoney = 1000

for i in range(N-1):
    if A[i] < A[i + 1]:
        
        iStock = iMoney // A[i]
        iMoney %= A[i]
        iMoney += iStock * A[i+1]
print(iMoney)

Solution (Python):
def main():
    n = int(input())
    A = list(map(int, input().split()))
    ans, b = 1000, 0
    def buy(a):
        nonlocal b, ans
        b += ans // a
        ans %= a
    def sell(a):
        nonlocal b, ans
        ans += b * a
        b = 0
    if A[0] < A[1]: buy(A[0])
    for i in range(1, n - 1):
        if A[i - 1] >= A[i] < A[i + 1]:
            buy(A[i])
        elif A[i - 1] <= A[i] > A[i + 1]:
            sell(A[i])
        else:
            continue
    if b > 0:
        sell(A[-1])
    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    n = int(readline())
    a = [0] + list(map(int, readline().split()))
    dp = [0] * (n + 1)
    dp[0] = 1000

    for i in range(1, n + 1):
        dp[i] = dp[i - 1]
        for j in range(1, i):
            s = dp[j] // a[j]
            m = s * a[i] + dp[j] % a[j]
            dp[i] = max(dp[i], m)

    print(dp[n])


if __name__ == '__main__':
    main()

Solution (Python):
n = int(input())
a = list(map(int, input().split()))

ans = 1000
for i in range(n - 1):
    if a[i] < a[i + 1]:
        ans = ans % a[i] + (ans // a[i]) * a[i + 1]

print(ans)

Solution (Python):
n = int(input())
al = list(map(int,input().split()))

kabu = 0
money = 1000
for i in range(n-1):
    if al[i] < al[i+1]:
        
        money += kabu * al[i]
        kabu = 0
        
        kabu += money // al[i]
        money = money % al[i]
    else:
        
        money += kabu * al[i]
        kabu = 0

print(money+ kabu*al[-1])

Solution (Python):
n = int(input())
al = list(map(int,input().split()))

kabu = 0
money = 1000
for i in range(n-1):
    if al[i] < al[i+1]:
        
        money += kabu * al[i]
        kabu = 0
        
        kabu += money // al[i]
        money = money % al[i]
    else:
        
        money += kabu * al[i]
        kabu = 0

print(money+ kabu*al[-1])

Solution (Python):
n = int(input())
a = [-1] + list(map(int, input().split()))



dp = [0] * (n + 1)
dp[0] = dp[1] = 1000
dp[2] = max(dp[0] % a[1] + (dp[0] // a[1]) * a[2], dp[1])

for i in range(1, n + 1):
    cand = dp[i - 1]
    for j in range(1, i):
        cand = max(cand, dp[j - 1] % a[j] + (dp[j - 1] // a[j]) * a[i])
    dp[i] = cand

print(dp[n])

Solution (Python):


N = int(input())
A = list(map(int, input().split()))
i = 0
M =1000
while i in range(N - 1):
    if A[i] >= A[i+1]:
        i = i + 1   
    else:
        m = (A[i+1] - A[i]) * (M // A[i])
        M = M + int(m)
        i = i + 1
print(M)

Solution (Python):
n = int(input())
k = list(map(int, input().split()))
m = 1000
s = 0
for i in range(n - 1):
    if k[i + 1] > k[i]:
        s = m // k[i]
        m += s * (k[i + 1] - k[i])
print(m)

Solution (Python):
N = int(input())
A = list(map(int, input().split()))

def sell(money,stock,price):
  money += price*stock
  stock = 0
  return money, stock

def buy(money,price):
  stock,money = divmod(money,price)
  return money,stock

money = 1000
stock = 0
for i in range(N):
  money, stock = sell(money,stock,A[i])
  if i<N-1 and A[i]<A[i+1]:
    money, stock = buy(money,A[i])
print(money)

Solution (Python):
import sys
imput = sys.stdin.readline

N = int(input())
a = list(map(int, input().split()))

money = 1000

for i in range(N-1):
  if a[i+1] > a[i]:
    k = money//a[i]
    money += a[i+1]*k - a[i]*k
    
print(money)

Solution (Python):
import sys

N = int(input())
A = list(map(int, sys.stdin.readline().rsplit()))

dp = [0] * N
dp[0] = 1000

for i in range(N - 1):
    dp[i + 1] = max(dp[i], (dp[i] // A[i]) * A[i + 1] + dp[i] % A[i])

print(dp[N - 1])

Solution (Python):
n = int(input())
A = list(map(int, input().split()))

money = 1000
stock = 0

for i in range(1, n):
    if A[i-1] > A[i]:
        money += stock * A[i-1]
        stock = 0
    else:
        stock += money // A[i-1]
        money %= A[i-1]
else:
    money += stock * A[-1]
    stock = 0

print(money)

Solution (Python):
a=[input() for i in range(2)]
a1=int(a[0])
a2=[int(i) for i in a[1].split()]

money=1000
kabu=0

for i in range(a1-1):
	if a2[i]<a2[i+1]:
		kabu=int(money/a2[i])
		money+=kabu*(a2[i+1]-a2[i])

print(money)

Solution (Python):
n = int(input())
a = [0] + list(map(int, input().split()))

'''
ans = 1000
for i in range(n - 1):
    x = a[i]
    y = a[i + 1]
    if x < y:
        k = ans // x
        ans %= x
        ans += k * y

print(ans)
'''

dp = [0] * (n + 10)
dp[1] = 1000
for i in range(2, n + 1):
    dp[i] = dp[i - 1]
    for j in range(1, i):
        x = dp[j] // a[j]
        y = dp[j] + (a[i] - a[j]) * x
        dp[i] = max(dp[i], y)

ans = dp[n]
print(ans)

Solution (Python):
n = int(input())
a = list(map(int, input().split()))

money = 1000
stock = 0

for i in range(n-1):
  if a[i+1] > a[i]:
    stock = money // a[i]
    money = money - stock * a[i] + stock * a[i+1]
    
print(money)