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()))
m = 1000
s = 0
for i in range(0,n):
    for j in range(i+1,n):
        if a[i] != a[j]:
            if a[i] >= a[j]:
                m = m + s *a[i]
                s = 0
                break
            else:
                s = s + m//a[i]
                m = m - m//a[i]*a[i]
                break

print(m+s*a[len(a)-1])

Solution (Python):
N = int(input())
money = 1000
M = N//2
prices = list(map(int, input().split()))
prices.append(0)
dp = [[0 for j in range(M+1)]for i in range(N+1)]
dp[0][0] = money
max_p = money

for i in range(1, N+1):
    for j in range(M+1):
        dp[i][j] = dp[i-1][j]
        if j > 0:
            for l in range(i):
                x = dp[l][j-1] % prices[l] + dp[l][j-1]//prices[l]*prices[i]
                if dp[i][j] < x:
                    dp[i][j] = x
            if max_p < dp[i][j]:
                max_p = dp[i][j]
print(max_p)

Solution (Python):
N = int(input())
A = list(map(int,input().split()))
money = 1000
cab = 0
lowprice = A[0]
check = True
for i in range(1,N):
    if(lowprice>A[i]):
        lowprice = A[i]
        check= True
    elif((lowprice<A[i]) and (check == True)):
        high_price = A[i]
        if(i<N-1):
            if(high_price > A[i+1]):
                cab=money//lowprice
                money-=(lowprice*cab)
                money+=(high_price*cab)
                cab = 0
                check = False
                lowprice = high_price
        else:
            cab=money//lowprice
            money-=(lowprice*cab)
            money+=(high_price*cab)
            cab = 0
            check = False
            lowprice = high_price
print(money)

Solution (Python):
N = int(input())
L = [0 for i in range(N)]
L = list(map(int,input().split()))


T = 0
M = 1000

I = 0
J = 0
while I < N-1:
    
    if I+J+1 > N or L[I+J] >= L[I+1+J]:
        M += (M//L[I]) * (L[I+J]-L[I])
        I += J+1
        J = 0
    else:
        if I+J+1 == N-1:
          M += (M//L[I]) * (L[I+J+1]-L[I])
          I += J+1
          J = 0
        else:J += 1

print(M)

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

fp = A[0]
tmp = 0
c = 1000
stock = 0
IsSearchTop = False
first = True
for i in range(1,N):

        if IsSearchTop:
            if fp <= A[i]:
                fp = A[i]
                if i == N-1:
                    c += stock * fp
            elif fp > A[i]:
                c += stock * fp
                stock = 0
                fp = A[i]
                IsSearchTop = False
        else:
            if fp >= A[i]:
                fp = A[i]
            elif fp < A[i]:
                stock += c // fp
                c -= stock * fp
                IsSearchTop = True
                fp = A[i]
                if i == N - 1:
                    c += stock * fp
print(c)

Solution (Python):
N=int(input())
A=list(map(int, input().split()))
B=[]
B.append(A[0])
for i in range(1,N):
    if A[i]!=B[-1]: B.append(A[i])
i=1
length=len(B)
while i<length-1:
    if B[i]>B[i-1] and B[i]<B[i+1] or B[i]<B[i-1] and B[i]>B[i+1]:
        B.pop(i)
        length-=1
    else:
        i+=1
yen=1000
kabu=0
for i in range(len(B)):
    if len(B)>=2 and B[0]<B[1]:
        if i%2==0 and i<len(B)-1:
            kabu=yen//B[i]
            yen=yen%B[i]
        elif i%2==1:
            yen=yen+kabu*B[i]
    else:
        if i%2==1 and i<len(B)-1:
            kabu=yen//B[i]
            yen=yen%B[i]
        elif i%2==0:
            yen=yen+kabu*B[i]
print(yen)

Solution (Python):
n=int(input())
a=list(map(int,input().split()))
ans=[1000]
m=1000
k=0
for i,num in enumerate(a):
	m=k*num+m
	k=0
	ans.append(m)
	if i<n-1:
		if num<a[i+1]:
			k=m//num
			m=m-k*num
print(max(ans))

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

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

is_start_increase = [0]*N
is_end_increase = [0]*N
is_increasing = [0]*N



























for i in range(N-1):
    if A[i] <= A[i+1]:
        is_increasing[i] = 1
if is_increasing[0] == 1:
    is_start_increase[0] = 1
for i in range(1, N):
    if is_increasing[i] == 1 and is_increasing[i-1] == 0:
        is_start_increase[i] = 1
    if is_increasing[i] == 0 and is_increasing[i-1] == 1:
        is_end_increase[i] = 1

money = 1000
stock = 0
stocks = []
for i in range(N):
    if i==N-1:
        
        money += stock * A[i]
        break
    if is_start_increase[i]:
        
        stock += money // A[i]
        money -= A[i] * stock
    if is_end_increase[i]:
        
        money += stock * A[i]
        stock = 0
    stocks.append(stock)

print(money)

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

A.append(0)

money = 1000
kau = 0

for i in range(N):
    if A[i] < A[i+1]:
        continue
    else:
        kabu = money//A[kau]
        money = money - A[kau]*kabu
        money = money + kabu*A[i]
        kau = i+1
        
print(max(money,1000))

Solution (Python):
n = int(input())
a = list(map(int, input().split()))
money = 1000
peak = []
botom = []
kabu = 0

if a[0] < a[1]:
    botom.append(0)
if a[n-1] >= a[n-2]:
    peak.append(n-1)
for i in range(1, n-1):
    if a[i] >= a[i-1] and a[i] > a[i+1]:
        peak.append(i)
    if a[i] <= a[i-1] and a[i] < a[i+1]:
        botom.append(i)

for i in range(n):
    if i in botom:
        kabu += money//a[i]
        money %= a[i]
    if i in peak:
        money += kabu*a[i]
        kabu = 0

print(money)

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

money = 1000
kabu = 0
while A[-1] <= A[-2]:
    A.pop()
    if len(A) == 1:
        break
t = [0] * len(A)
for i in range(1, len(A)):
    if A[i] > A[i-1]:
        t[i] = 1
    elif A[i] < A[i-1]:
        t[i] = -1
    else:
        t[i] = 0

n_move = 1

for i in range(len(A) - 1):
    if n_move == 1 and t[i] != 1 and t[i+1] == 1:
        kabu += money // A[i]
        money -= A[i] * (money // A[i])
        
        n_move = 1 - n_move
    elif n_move == 0 and t[i] != -1 and t[i+1] == -1:
        money += A[i] * kabu
        kabu = 0
        n_move = 1 - n_move
print(money + kabu * A[-1])

Solution (Python):
N = int(input())
A = [int(x) for x in input().split()]
value = 1000
current = 0
stocks = 0
for i in range(N-1):
    if A[i] < A[i+1] :
        h = value//A[i]
        stocks+=h
        value = value - h*A[i]
    if A[i]==max(A[i:]) :
        value = value + stocks*A[i]
        stocks = 0
    elif A[i] > A[i+1]:
        value = value + stocks*A[i]
        stocks = 0
value = value + stocks*A[N-1]
print(value)

Solution (Python):
n = int(input())
lst = [int(i) for i in input().split()]

stock = 0
money = 1000
for i in range(n):
  if i < n - 1:
    if lst[i] <= lst[i + 1]:
      stock += money // lst[i]
      money = money % lst[i]
    if lst[i] > lst[i + 1]:
      if stock > 0:
        money += stock * lst[i]
        stock = 0
  if i == n - 1:
    if stock > 0:
      money += stock * lst[i]
      stock = 0
  
print(money)

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

def chk(i,A):
    bl = False
    for j in range(i+1,n):
        if A[j] > A[i]:
            bl = True
            break
        elif A[j] < A[i]:
            break
    return bl

def buy(cash, kabu, ai):
    num = int(cash / ai)
    cash -= num * ai
    kabu += num
    return cash,kabu

def sell(cash, kabu, ai):
    cash += kabu * ai
    kabu = 0 
    return cash,kabu

cash = 1000
kabu = 0
for i in range(n):
    if chk(i,A):
        (cash, kabu) = buy(cash, kabu, A[i])
    else:
        (cash, kabu) = sell(cash, kabu, A[i])

print(cash)

Solution (Python):

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

state = 1  
cur = (1000, 0)  
for i in range(N - 1):
    if state == 1 and X[i + 1] > X[i]:
        n = cur[0] // X[i]
        cur = (cur[0] - n * X[i], cur[1] + n)
        state = 0
    elif state == 0 and X[i + 1] < X[i]:
        cur = (cur[0] + cur[1] * X[i], 0)
        state = 1


print(cur[0] + cur[1] * X[-1])

Solution (Python):
n = int(input())
rates = list(map(int, input().split(' ')))
pocket = 1000
kabu = 0

for i,rate in enumerate(rates):
  day = i+1
  if day == n:
    pocket += kabu*rate
    kabu = 0
    break
  if rate < rates[i+1]:
    
    buy_kabu = pocket // rate
    pocket -= buy_kabu*rate
    kabu += buy_kabu
  elif rate > rates[i+1]:
    
    pocket += kabu*rate
    kabu = 0

print(pocket)

Solution (Python):
n = int(input())
a = list(map(int, input().split()))
pair = []
l = -1
r = -1
flg = False
for i in range(n-1):
    if flg == False:
        if a[i+1]-a[i]>=0:
            l = i
            flg = True
        else:
            pass
    else:
        if a[i+1]-a[i]>=0:
            pass
        else:
            r = i
            flg = False
            pair.append((a[l],a[r]))
if flg:
    r = i+1
    pair.append((a[l],a[r]))

money = 1000
stock = 0
max_rate = 0
for fr,to in pair: 
    
    max_rate = to/fr
    
    buy = money//fr
    stock += buy
    money -= buy*fr
    
    sold = stock
    money += sold*to
    stock -= sold
    
    
print(money)

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

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

start = 0
money = 1000

for i in range(N - 1):
    if A[i + 1] > A[i]:
        buy = money // A[i]
        money -= A[i] * buy
        money += buy * A[i + 1]

print(money)

Solution (Python):
n = int(input())
al = list(map(int, input().split()))
ald = []
st = 0
mn = 1000
for i in range(1, n):
    ald.append(al[i] - al[i - 1])
if ald[0] > 0:
    st += mn // al[0]
    mn -= (mn // al[0]) * al[0]
elif ald[0] < 0:
    mn += st * al[0]
    st = 0
for i in range(1, n - 1):
    if ald[i] > 0:
        st += mn // al[i]
        mn -= (mn // al[i]) * al[i]
    elif ald[i] < 0:
        mn += st * al[i]
        st = 0
mn += st * al[n - 1]
print(mn)

Solution (Python):
N = int(input())
A = list(map(int, input().split()))
count = 0
money = 1000
kabu = 0
temp = A[0]
while count < N:
    if A[count] > temp:
        kabu = money // temp
        money = money % temp
        money += kabu * A[count]
        kabu = 0
    temp = A[count]
    count += 1

print(money)

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

n = int(input())

AA = [int(a) for a in input().split()]
c = 0
updwn=[None]*(n-1)
for a in AA:
    if c ==0:
        c +=1
        base = a
        continue
    if a - base >= 0:
        updwn[c-1] = True
        base = a
    else:
        updwn[c-1] = False
        base = a
    c += 1
updwn+=[False, False]
base = False
total = 1000
stock = 0

for i in range(n):
    if updwn[i] == True and base == False:
        tdcost= AA[i]
        stock = total // tdcost
        base_cost = tdcost
    elif updwn[i-1] == True and updwn[i]==False:
        tdcost=AA[i]
        total += (tdcost - base_cost)*stock
        stock = 0
    else:
        pass
    base = updwn[i]
print(total)

Solution (Python):
def resolve():
    N = int(input())
    A = list(map(int, input().split()))
    stocks = 0
    money = 1000
    i = 0
    while i < N:
        buy = i
        while buy < N-1 and A[buy] > A[buy+1]:
            buy += 1
        sell = buy
        while sell < N-1 and A[sell] <= A[sell+1]:
            sell += 1
        if buy == sell:
            print(money)
            return
        
        stocks = money//A[buy]
        money = money - stocks*A[buy]
        money += stocks*A[sell]
        stocks = 0
        i = sell+1
    print(money)
    

if '__main__' == __name__:
    resolve()

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

have_money = 1000
have_stack = 0

next_index = 1  


most_cheap = a_lst[0]
for i in range(1, n):
    if a_lst[i] > most_cheap:
        have_stack = have_money // most_cheap
        have_money = have_money % most_cheap
        break
    if i >= n:
        next_index += 1
        break
    most_cheap = a_lst[i]
    next_index += 1


while next_index < n:
    
    most_expensive = a_lst[next_index]
    while next_index < n:
        if a_lst[next_index] < most_expensive or next_index == n - 1:
            have_money += have_stack * most_expensive
            have_stack = 0
            break
        most_expensive = a_lst[next_index]
        next_index += 1
    if next_index >= n - 1:
        break

    most_cheap = a_lst[next_index]
    while next_index < n:
        if a_lst[next_index] > most_cheap:
            have_stack = have_money // most_cheap
            have_money = have_money % most_cheap
            break
        most_cheap = a_lst[next_index]
        next_index += 1

print(have_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 += stock * A[i]
        stock = 0
    elif money >= A[i]:
        stock = money // A[i]
        money -= stock * A[i]
print(stock * A[n-1] + money)

Solution (Python):
n = int(input())
lst1 = [0] + list(map(int, input().split()))
lst0 = []
for i in range(n):
  if lst1[i] != lst1[i + 1]:
    lst0.append(lst1[i + 1])
lst0.append(0)

if lst0[0] < lst0[1]:
  phase = 'u'
else:
  phase = 'd'
lst0 = [10000] + lst0

n = len(lst0)
lst2 = []
for i in range(n - 2):
  if lst0[i] < lst0[i + 1] and lst0[i + 1] > lst0[i + 2]:
    lst2.append(lst0[i + 1])
  elif lst0[i] > lst0[i + 1] and lst0[i + 1] < lst0[i + 2]:
    lst2.append(lst0[i + 1])

kane = 1000
kabu = 0
for i in range(len(lst2)):
  if i % 2 == 0:
    x = kane // lst2[i]
    kane %= lst2[i]
    kabu += x
  else:
    kane += (lst2[i] * kabu)
    kabu = 0
print(kane)

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

v=list(map(int,input().split()))
l=list()
prev=0
for i in v:
  if prev!=i:
    l.append(i)
    prev=i
n=len(l)
if n==1:
  print(1000)
else: 
  d=list()
  if l[0]>l[1]:
      d.append(l[0])
  if l[0]<l[1]:
      d.append(l[0])
  for i in range(1,n-1):
    if l[i-1]<l[i] and l[i+1]<l[i]:
      d.append(l[i])
    if l[i-1]>l[i] and l[i+1]>l[i]:
      d.append(l[i])
  if l[-1]>l[-2]:
      d.append(l[-1])
  if l[-1]<l[-2]:
      d.append(l[-1])
  
  n=len(d)
  p=1000
  if n>1:
    i=1
    while(i<n):
      if d[i-1]<d[i]:
        z=(p//d[i-1])*d[i]
        r=p%d[i-1]
        i+=2
        if z+r>p:
        	p=z+r
      else:
        i+=1
    print(p)
  else:
    print(p)

Solution (Python):
def resolve():
  N = int(input())
  A = [int(x) for x in input().split(" ")]

  diff_of_rate = [0]*(N-1)
  diff_of_rate = []
  diff_of_rate.append({"index": 0, "diff": 0, "price": A[0]})
  for i in range(N-1):
    if (diff_of_rate[-1]["diff"] <= 0 and A[i+1] - A[i] <= 0) or (diff_of_rate[-1]["diff"] >= 0 and A[i+1] - A[i] >= 0):
      diff_of_rate[-1]["index"] = i+1
      diff_of_rate[-1]["diff"] += A[i+1] - A[i]
      diff_of_rate[-1]["price"] = A[i+1]
    else:
      diff_of_rate.append({
        "index": i+1,
        "diff": A[i+1] - A[i],
        "price": A[i+1]
      })

  

  
  money = 1000
  stock = 0
  price = A[0]

  
  if diff_of_rate[0]["diff"] > 0:
    stock += money//price
    money = money%price
    
  for index, diff in enumerate(diff_of_rate):
    if diff["diff"] < 0 and index < len(diff_of_rate)-1:
      
      stock += money//diff["price"]
      money = money%diff["price"]
    else:
      
      money += stock*diff["price"]
      stock = 0

  print(money)

if __name__ == "__main__":
  resolve()

Solution (Python):
n=int(input())
a=[int(x) for x in input().split()]
buy=[]
out=[]
if a[0]<a[1]:
  buy.append(a[0])
for i in range(1,n-1):
  if a[i-1]>=a[i] and a[i]<a[i+1]:
    buy.append(a[i])
  if a[i-1]<a[i] and a[i]>=a[i+1]:
    out.append(a[i])
if a[n-1]>a[n-2]:
  out.append(a[n-1])

m=1000
k=len(buy)
for j in range(k):
  stock=m//buy[j]
  m+=(out[j]-buy[j])*stock
print(m)

Solution (Python):
def resolve():
    N = int(input())
    A = list(map(int,input().split()))
    A.append(A[-1] - 1)
    A_m = [A[0] + 1]
    A_m.extend(A)
    
    Buy_Sell = [ 0 for _ in range(N)]

    for i in range(1,N+1):
        if A_m[i] >= A_m[i-1] and A_m[i] > A_m[i+1]:
            Buy_Sell[i-1] = -1        
        if A_m[i] <= A_m[i-1] and A_m[i] < A_m[i+1]: 
            Buy_Sell[i-1] = 1         
    
    money = 1000
    stock = 0
    for i in range(N):
        if(Buy_Sell[i]) == 1:
            stock += money // A[i]
            money = money % A[i]
            
        if(Buy_Sell[i]) == -1:
            money += stock * A[i]
            stock = 0
    print(money)
resolve()

Solution (Python):
def main():
    n = int(input())
    A = [int(x) for x in input().split()]
    money = 1000
    kabu_c = 0
    l = list()
    for i in range(n-1):
        if A[i+1] - A[i] > 0:
            l.append(1)
        else:
            l.append(0)
    for idx, i in enumerate(l):
        if i == 1 and money - A[idx] >= 0:
            kabu_c = money // A[idx]
            money = money - (kabu_c * A[idx])
        if i == 0:
            money = money + (kabu_c * A[idx])
            kabu_c = 0
    if kabu_c > 0:
        money = money + (kabu_c * A[n-1])
    print(money)

if __name__ == '__main__':
    main()

Solution (Python):

"""
Created on Sat Jul 25 18:38:36 2020

@author: Paras
"""

n = int(input())
stocks = list(map(int, input().split()))
yens = 1000
curr_stocks = 0

for i in range(n-1):
    if stocks[i+1]>stocks[i]:
        yens=(yens//stocks[i])*(stocks[i+1])+(yens-((yens//stocks[i])*stocks[i]))

print(yens)

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


money = 1000
stock = 0

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

    

money += stock * arr[-1]

print(money)

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

delta_a = [0] * (n-1)
for i in range(n-1):
  delta_a[i] = a[i+1] - a[i]

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

if stock != 0:
  money += stock * a[n-1]
print(money)

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

b=[]
m=0
for i in range(n):
    if m==a[i]:
        continue
    m=a[i]
    b.append(a[i])

c=[]
c.append(b[0])
vec=0

for i in range(1,len(b)):
    if b[i]>b[i-1]:
        if vec==1 or vec==0:
            vec=1
            continue
        else:
            vec=1
            c.append(b[i-1])
    elif b[i]<b[i-1]:
        if vec==2 or vec==0:
            vec=2
            continue
        else:
            vec=2
            c.append(b[i-1])
c.append(b[-1])

money=1000
for i in range(1,len(c)):
    if c[i]>c[i-1]:
        money=money+(money//c[i-1])*(c[i]-c[i-1])

print(money)

Solution (Python):
n = int(input())
a_li = list(map(int,input().split()))
low = a_li[0]
high = a_li[0]
old = a_li[0]
yen = 1000
for i in range(1,n):
    if old < a_li[i]:
        div, yen = divmod(yen, old)
        yen += div * a_li[i]
    old = a_li[i]
print(yen)

Solution (Python):

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

money = 1000
kabu = 0

for i in range(n):

    if i < n - 1 : 

        if a_list[i] < a_list[i + 1] :

            if money >= a_list[i] :
                kabu = money // a_list[i]
                money = money % a_list[i]
        else :
            if kabu != 0 :
                money = money + kabu * a_list[i]
                kabu = 0
    else :
        if kabu != 0 :
            money = money + kabu * a_list[i]
            kabu = 0

print(money)

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

money = 1000
stack = 0
up = []
last_high = 0
high = 0
low = a[0]

for i in range(n):
    if i == 0:
        up.append(-1)
    elif a[i] < a[i-1]:
        up.append(-1)
    elif a[i] >= a[i-1]:
        if i == n-1:
            up.append(1)
        elif a[i] > a[i+1]:
            up.append(1)
        else:
            up.append(0)

for i in range(n):
    if up[i] == 1:
        high = a[i]
        for j in range(last_high, i):
            if up[j] == -1:
                low = a[j]
        stack = money // low
        money %= low
        money += stack * high

print(money)

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

def main():
    N = int(readline())
    A = [int(i) for i in readline().split()]

    now = A[0]
    pair = []
    mode = "up"
    for i in range(N-1):
        if mode == "up":
            if A[i+1] > A[i]:
                continue
            elif A[i+1] == A[i]:
                continue
            else:
                pair.append((now, A[i]))
                mode = "down"
        else:
            if A[i+1] < A[i]:
                continue
            elif A[i+1] == A[i]:
                continue
            else:
                now = A[i]
                mode = "up"

    if mode == "up":
        if now < A[-1]:
            pair.append((now, A[-1]))

    money = 1000
    stock = 0
    for buy, sell in pair:
        stock += money // buy
        money -= buy * stock
        money += sell * stock
        stock = 0

    print(money)


if __name__ == "__main__":
    main()

Solution (Python):
import math
a = input()
b = input().split(" ")
c = []
for i in b:
  c.append(i)
money = 1000
senet = 0
chk = 0
c.sort(reverse=True)
for i in range(int(a)):
  for j in range(int(a)):
    if j != int(a)-1:
      if b[j] >= b[j+1]:
        pass;
      else:
        chk = 1 
  if chk == 0:
    break;
  elif i == int(a)-1:
    money = money + (senet * int(b[i]))
  elif i == 0:
    if int(b[i]) < int(b[i+1]):
      senet += math.floor(money / int(b[i]))
      money = money-(math.floor(money / int(b[i]))*int(b[i]))
  elif int(b[i]) < int(b[i+1]):
      senet += math.floor(money / int(b[i]))
      money = money-(math.floor(money / int(b[i]))*int(b[i]))
  elif int(b[i]) > int(b[i+1]):
    money += senet * int(b[i])
    senet = 0 
  elif int(b[i]) == int(b[i+1]):
    pass;
print(money)

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

def ask_judge(asset_now, position):
    if ask[i]:
        position += asset_now // A[i]
        asset_now -= asset_now // A[i] * A[i]    
    return asset_now, position

def bid_judge(asset_now, position):
    if bid[i]:
        asset_now += position * A[i]    
        position = 0
    return asset_now, position


asset_now = 1000

ask = [True if A[i+1] - A[i] > 0 else False for i in range(N-1)]
bid = [True if A[i+1] - A[i] < 0 else False for i in range(N-1)]
position = 0

for i in range(N):
    if i == 0:
        asset_now, position = ask_judge(asset_now, position)
    elif i == N-1:
        if position > 0:
            asset_now += position * A[N-1]
    else:
        asset_now, position = ask_judge(asset_now, position)
        asset_now, position = bid_judge(asset_now, position)

print(asset_now)

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

money = 1000

init = A[0]
maxA = 0
for i in range(1,len(A)):
    if A[i-1] > A[i]:
        if maxA != 0:
            money = ((money // init) * maxA) + (money % init)
            maxA = 0
        init = A[i]
    elif init < A[i]:
        maxA = A[i]

if init < A[-1]:
    money = ((money // init) * maxA) + (money % init)

print(money)

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

ans=1000
kabu=0
flag=0

for i in range(n-1):
    if a[i]<a[i+1]:
        if flag <=0:
            kabu=int(ans/a[i])
            ans-=(kabu*a[i])
            
        flag=1
    elif a[i]>a[i+1]:
        if flag >0:
            ans+=(kabu*a[i])
            
        flag=-1
    else:
        if flag>0:
            flag=2
        else:
            flag=-2
    if i==(n-2) and flag>0:
        ans+=(kabu*a[i+1])
        

print(ans)

Solution (Python):

import sys

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

M = 1000
kabu = 0

cur = A[0]

for i in range(1,N):
    if cur > A[i]:
        
        M = M + kabu * cur
        kabu = 0
    if cur < A[i]:
        
        if M >= cur:
            kabu = M // cur
            M = M % cur
    cur = A[i]




M = M + kabu * cur
print(M)

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








hold = False
money = 1000
kabu = 0
lastval = 0
for i in range(1, len(A)):
 

    if hold == False and A[i-1] < A[i]:
        hold = True
        kabu = money // A[i -1]
        money = money % A[i -1]
        lastval = A[i-1]

    if hold == True and A[i-1] > A[i]:
        hold = False
        money = money + kabu * A[i-1]
        kabu = 0


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

print(money)

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

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


is_up = False
buy_sell = []
for i in range(N-1):
    if A[i] > A[i+1]:
        if is_up:
            buy_sell.append(A[i])
        is_up = False
    elif A[i] < A[i+1]:
        if not is_up:
            buy_sell.append(A[i])
        is_up = True
    else:
        pass
else:
    if is_up:
        buy_sell.append(A[-1])


ln = len(buy_sell)
money = 1000
stock = 0
for i in range(ln):
    if i % 2 == 0:
        stock = money // buy_sell[i]
        money = money - stock * buy_sell[i]
    else:
        money += stock * buy_sell[i]

print(money)

Solution (Python):

def main():
    money = 1000
    kabu = 0
    n = int(input())
    kabu_price = [0] + list(map(int,input().split()))
    up = False
    for i in range(1,n):

        if  kabu_price[i+1] > kabu_price[i] and not up:
            buy_kabu = money // kabu_price[i]
            kabu += buy_kabu
            money -= buy_kabu * kabu_price[i]
            up = True

        if kabu_price[i+1] < kabu_price[i] and up:
            sell_kabu = kabu
            money += sell_kabu * kabu_price[i]
            kabu -= sell_kabu
            up = False
        
        
    money += kabu * kabu_price[n]
    print(money)





if __name__ == '__main__':
    main()

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

def kai(kane_kabu, kakaku):
  kabu = int(kane_kabu[0] / kakaku)
  kane = kane_kabu[0] % kakaku
  return [kane, kabu]

def uri(kane_kabu, kakaku):
  kane = kane_kabu[1] * kakaku + kane_kabu[0]
  kabu = 0
  return [kane, kabu]


kane_kabu = [1000, 0]

for i in range(n-1):
  if kane_kabu[1] == 0:
    kae = 1
    ure = 0
  else:
    kae = 0
    ure = 1
  for j in range(i+1, n):
    if a[i] >= a[j] and kane_kabu[1] == 0:
      kae = 0
      break
    elif a[i] < a[j] and kane_kabu[1] == 0:
      break
    if a[i] <= a[j] and kane_kabu[1] > 0:
      ure = 0
      break
    elif a[i] > a[j] and kane_kabu[1] > 0:
      break
  if ure == 1:
    kane_kabu = uri(kane_kabu, a[i])
  elif kae == 1:
    kane_kabu = kai(kane_kabu, a[i])

if kane_kabu[1] > 0:
  kane_kabu = uri(kane_kabu, a[n-1])
print(kane_kabu[0])

Solution (Python):


n = int(input())
A = list(map(int, input().split()))
i = 0
j = 0
money = 1000
while True:
  i = i+j
  j = 0
  while A[i] >= A[i+1]:
    i += 1
    if i + 1 == n:
      break
    
  if i + 1 == n:
    break
  while A[i+j] <= A[i+j+1]:
    j += 1
    if i+j+1 == n:
      break
    
  if i+j+1 == n:
    money += (money // A[i]) * (A[i+j] - A[i])
    break
  money += (money // A[i]) * (A[i+j] - A[i])
print(money)

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

d = 1000
s = 0

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

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

sum = 1000
kabu = 0

for k in range(K):
    if k+1 ==K:
        sum +=kabu*A[K-1]
        break
    if A[k]<A[k+1] and A[k]<=sum:
        S = int(sum/A[k])
        sum = sum-A[k]*S
        kabu +=S
    elif A[k]>A[k+1] and kabu != 0:
        sum = sum + kabu * A[k]
        kabu = 0
    

print(sum)

Solution (Python):
def d():
    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]:
            stock += money // A[i-1]
            money -= A[i-1] * (money // A[i-1])
            

        elif A[i-1] > A[i]:
            money += stock * A[i-1]
            stock = 0
            

    if A[N-2] <= A[N-1]:
        money += stock * A[N-1]
        stock = 0
        

    print(money)



if __name__ == "__main__":
    d()

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

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

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

m = 1000
s = a[0]
kabu = 0
zankin = m
for i in range(1, n):
    if a[i] > s:
        kabu = m//s
        zankin = m%s
        m = a[i] * kabu + zankin
    s = a[i]
print(m)