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):
import math


def a():
    x = int(input())

    if x < 600:
        print(8)
    elif x < 800:
        print(7)
    elif x < 1000:
        print(6)
    elif x < 1200:
        print(5)
    elif x < 1400:
        print(4)
    elif x < 1600:
        print(3)
    elif x < 1800:
        print(2)
    else:
        print(1)


def b():
    a, b, c = map(int, input().split())
    k = int(input())
    count = 0

    while b <= a:
        b *= 2
        count += 1

    while c <= b:
        c *= 2
        count += 1
    if count <= k:
        print('Yes')
    else:
        print('No')


def c():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))

    for i in range(k, n):
        if a[i] > a[i-k]:
            print('Yes')
        else:
            print('No')


def d():
    n = int(input())
    a = list(map(int, input().split()))
    a = [a[1]] + a + [a[n-2]]
    money = 1000
    kabu = 0
    for i, v in enumerate(a[1:n+1], 1):
        if (v > a[i-1] and v >= a[i+1]) or (v >= a[i-1] and v > a[i+1]):
            
            money += kabu * v
            kabu = 0
        elif (v < a[i-1] and v <= a[i+1]) or (v <= a[i-1] and v < a[i+1]):
            
            temp = money // v
            money -= temp * v
            kabu += temp
        
    money += kabu * a[n]
    print(money)





d()

Solution (Python):
money = 1000
kabu = 0

input()
A = [int(x) for x in input().strip().split(" ")]
As = [[]]

for i, a in enumerate(A):
    if len(As[-1]) == 0:
        As[-1].append(a)
    elif As[-1][-1] <= a:
        As[-1].append(a)
    else:
        As.append([a])
As = [As_ for As_ in As if len(As_) > 1]
for As_ in As:
    kabu, money = divmod(money, As_[0])
    money += kabu * As_[-1]
print(money)

Solution (Python):
n = int(input())
a = list(map(int,input().split()))
lis = [0]*n
for i in range(n-1):
    if a[i] > a[i+1]:
        lis[i] = -1
b = a[::-1]
for i in range(n-1):
    if b[i] < b[i+1]:
        if lis[n-i-1] == -1:
            pass
        else:
            lis[n-i-1] = 1
lis[-1] = -1
sw = 0
for i in range(1,n):
    if a[0] < a[i]:
        sw = 1
        break
    if a[0] > a[i]:
        sw = 0
        break
if sw == 1:
    lis[0] = 1
m = 1000
k = 0
for i in range(n):
    if lis[i] == 1:
        k += m//a[i]
        m = m%a[i]
    elif lis[i] == -1:
        m += k*a[i]
        k = 0
print(m)

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]*(a[i+1]-a[i])
print(ans)

Solution (Python):
N=int(input())
A=list(map(int,input().split()))
B=[0 for i in range(N-1)]
for i in range(N-1):
  if A[i]<A[i+1]:
    B[i]=1
B=[0]+B
money=1000
tmp=0
up=[]
down=[]
for i in range(N-1):
  if B[i]==0 and B[i+1]==1:
    up.append(i)
  if B[i]==1 and B[i+1]==0:
    down.append(i)
import bisect   
if up:
  if down==[]:
    down.append(N-1)
  if down!=[] and down[-1]<up[-1]:
    down.append(N-1)

for i in range(len(up)):
  k=bisect.bisect_left(down,up[i])
  money+=(A[down[k]]-A[up[i]])*(money//A[up[i]])     
print(money)

Solution (Python):
from sys import stdin, stdout
import heapq
import cProfile
from collections import Counter, defaultdict, deque
from functools import reduce
import math


def get_int():
    return int(stdin.readline().strip())


def get_tuple():
    return map(int, stdin.readline().split())


def get_list():
    return list(map(int, stdin.readline().split()))

n = get_int()
ls = get_list()
peak_pts = []
inc = True if ls[1]>ls[0] else False
if ls[1]>ls[0]:
    peak_pts.append(0)
i = 1
while i<n:
    if ls[i]>=ls[i-1]:
        if not inc:
            peak_pts.append(i - 1)
            inc = not inc
    else:
        if inc:
            peak_pts.append(i-1)
            inc = not inc
    i += 1
if ls[-1]>=ls[-2]:
    peak_pts.append(n-1)


profit = 1000
le = len(peak_pts)
ava_bought,ava_sell = 1000,0
for ind in range(0,le,2):
    i = peak_pts[ind]
    if ind+1<le:
        midprofit = 0

        
        j = i
        totalshares = 0
        while j<peak_pts[ind+1]:
            shares = (ava_bought//ls[j])
            ava_bought -= shares*ls[j]
            midprofit -= shares*ls[j]
            ava_sell += shares*ls[j]
            totalshares += shares
            if ava_bought==0: break
            if j+1<n and ls[j+1]>ls[j]: break
            j += 1

        
        j = peak_pts[ind+1]
        midprofit += ls[j]*totalshares
        if midprofit>0:
            profit += midprofit
        ava_bought = profit
        
print(profit)

Solution (Python):
import sys
import itertools


def resolve(in_):
    n = int(next(in_))
    a = tuple(map(int, next(in_).split()))
    
    m = 1000
    s = 0

    b, c = itertools.tee(a)
    next(c)
    for x, y in zip(b, c):
        
        if x < y:
            ss, mm = divmod(m, x)
            m = mm
            s += ss
        elif x > y:
            mm = x * s
            m += mm
            s = 0
        
    else:
        mm = y * s
        m += mm
        s = 0
        

    return m


def main():
    answer = resolve(sys.stdin.buffer)
    print(answer)


if __name__ == '__main__':
    main()

Solution (Python):
import math

n = int(input())
aL = list(map(int, input().split(" "))) + [0]
bL = ["NO" for _ in range(n)]

mk = 0
mm = 1000

up = False
for i in range(n):
    cr = aL[i]
    nx = aL[i + 1]

    if up:
        if cr > nx:
            up = False
            mm += mk * cr
            mk = 0
    else:
        if cr < nx:
            up = True
            mk = mm // cr
            mm = mm % cr

print(mm)

Solution (Python):
n = int(input())
la = [10000]+[int(w) for w in input().split()]+[-1]

money = 1000

cheap = la[1]
for i in range(2, len(la)):
    if la[i] >= la[i-1]:
        cheap = min(cheap, la[i-1])
        continue
    if la[i-1] >= la[i-2]:
        kabu = money//cheap
        money += kabu*(la[i-1] - cheap)
        cheap = la[i]
    cheap = min(cheap, la[i])
print(money)

Solution (Python):
N = int(input())
A = list(map(int, input().split()))
asset = 1000
stock = 0

for i in range(N):
    if i == N - 1:
        asset += stock * A[i]
        stock = 0
    else:
        if A[i] < A[i + 1]:
            r, v = divmod(asset, A[i])
            
            stock += r
            asset = v
        else:
            asset += stock * A[i]
            stock = 0
print(asset)

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

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

a = a + [0]
b = 1000
c = 0
for i in range(1, n):
    numb = a[i-1]
    numa = a[i]
    numaa = a[i+1]
    if numb < numa and b > c*100:
        c = b//numb
        b = b%numb
    if numa > numaa:
        b += c*numa
        c = 0

print(b)

Solution (Python):


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

money = 1000
kabu = 0

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

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

stock = 0
money = 1000
prev_trend = a[1] - a[0]

if prev_trend > 0:
    stock += money // a[0]
    money -= a[0] * (money // a[0])

if len(a) > 2:
    for i in range(1, n-1):
        next_trend = a[i+1] - a[i]
        if prev_trend >= 0 and next_trend < 0:
            money += a[i] * stock
            stock = 0
        elif prev_trend <= 0 and next_trend > 0:
            stock += money // a[i]
            money -= a[i] * (money // a[i])
        prev_trend = a[i+1] - a[i]

money += a[n-1] * stock
stock = 0

print(money)

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

p = 1000
n = 0
for i in range(N-1):
    if A[i+1] > A[i]:
        n += p//A[i]
        p = p % A[i]

    if A[i+1] < A[i]:
        p += n*A[i]
        n = 0

p += n*A[-1]
print(p)

Solution (Python):

import numpy as np
import sys
from collections import deque
from collections import defaultdict
import heapq
import collections
import itertools
import bisect
from scipy.special import comb
import copy
sys.setrecursionlimit(10**6)


def zz():
    return list(map(int, sys.stdin.readline().split()))


def z():
    return int(sys.stdin.readline())


def S():
    return sys.stdin.readline()[:-1]


def C(line):
    return [sys.stdin.readline() for _ in range(line)]


N = z()
A = zz()

diff = [0]*(N-1)
prev = A[0]
for i in range(1, N):
    diff[i - 1] = A[i] - A[i - 1]
ans = 0

for n in range(N):
    money = 1000
    kabu = 0
    for i in range(N):
        if (i == n):
            money += kabu*A[i]
            kabu = 0
            ans = max(ans, money)
            
            break

        if (diff[i] > 0):
            buy_kabu = (money//A[i])
            money -= (A[i]*buy_kabu)
            kabu += buy_kabu
        else:
            money += kabu*A[i]
            kabu = 0

        
print(ans)

Solution (Python):

import sys
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
read = sys.stdin.buffer.read
sys.setrecursionlimit(10 ** 7)
INF = float('inf')

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


pre = [0] * N
pre_index = 0
old_a = A[0]
if A[0] > A[1]:
    old_coef = -1
elif A[0] < A[1]:
    old_coef = 1
else:
    old_coef = 0

for i in range(1, N):
    if A[i] > old_a:
        coef = 1
    elif A[i] < old_a:
        coef = -1
    else:
        coef = 0
    if coef != 0 and coef != old_coef:
        for j in range(pre_index, i):
            pre[j] = i - 1
        pre_index = i
        old_coef = coef
    old_a = A[i]
for j in range(pre_index, N):
    pre[j] = N - 1


shojikin = 1000
stock = 0
if A[0] < A[pre[0]]:
    q, mod = divmod(shojikin, A[0])
    stock += q
    shojikin = mod
elif pre[0] == N - 1:
    
    print('1000')
    quit()



pre = list(set(pre))
pre.sort()

for deal_index in pre:
    if stock:
        shojikin += stock * A[deal_index]
        stock = 0
        
    else:
        q, mod = divmod(shojikin, A[deal_index])
        stock += q
        shojikin = mod
        

if stock:
    shojikin += stock * A[deal_index]
    stock = 0
print(shojikin)

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

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

Budget = 1000
Bond = 0

for n in range(len(A)-1):
  if A[n] < A[n+1]:
    Bond = Budget//A[n]
    Budget = (Budget - Bond*A[n]) + Bond*A[n+1]
    
print(Budget)

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

kabu=0
money=1000
x=x-1
lastday=0
for i in range(len(A)):
    if A[x-i]>A[x-i-1]:
        lastday=x-i
        break
    
for i in range(lastday):
    if A[i]<A[i+1]:
        buy=money//A[i]
        money-=A[i]*buy
        kabu+=buy
    elif A[i]>A[i+1]:
        money+=A[i]*kabu
        kabu=0

money+=A[lastday]*kabu
print(money)

Solution (Python):
N=int(input())
A=list(map(int,input().split()))
mochi=1000
x=A[0]
y=0
k=0
kabu=0
for i in range(1,N):
    if i<N-1:
        if A[i-1]<=A[i] and A[i]>=A[i+1]:
            x=A[i]
            y=min(A[k:i])
            kabu=mochi//y
            mochi-=kabu*y
            mochi+=kabu*x
            k=i
    else:
        if A[i-1]<A[i]:
            x=A[i]
            y=min(A[k:i])
            kabu=mochi//y
            mochi-=kabu*y
            mochi+=kabu*x
            k=i

print(mochi)

Solution (Python):


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

for i in range(0,N-1):
    if( A[i] < A[i+1] ):
        cash += cash // A[i] * (A[i+1] - A[i])

print(cash)

Solution (Python):

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

Solution (Python):

n = int(input())
a = list(map(int, input().split()))
money = 1000
stocks = 0
signal = 0
for i in range(len(a)-1):
  if signal == 0:
    if a[i+1] > a[i]:
      stocks, money = divmod(money, a[i])
      signal = 1
      
  else:
    if a[i+1] < a[i]:
      money += stocks * a[i]
      stocks = 0
      signal = 0
      
money += stocks*a[-1]
print(money)

Solution (Python):








import sys

N = int(sys.stdin.readline())

A = tuple(map(int,sys.stdin.readline().split())) 

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

Solution (Python):
def solve():
    n = int(input())
    a = list(map(int, input().split()))
    s = [0] * n
    for i in range(n - 1):
        if a[i + 1] > a[i]:
            s[i + 1] = 1
        elif a[i + 1] == a[i]:
            continue
        else:
            s[i + 1] = -1
    
    tak = 1000
    stock = 0
    for i in range(n - 1):
        if s[i + 1] == 1 and not stock:
            stock = tak // a[i]
            tak = tak % a[i]
        elif s[i + 1] == -1 and stock:
            tak += stock * a[i]
            stock = 0
    if s[-1] >= 0:
        tak += a[-1] * stock
    print(tak)


solve()

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

l = []
s = 0
for i in range(N-1):
    if A[i] > A[i+1]:
        l.append([s,i])
        s = i+1
    else:
        continue

l.append([s,N-1])

ans = 1000
for s,e in l:
    kabu = (ans//A[s])
    ans += (A[e]-A[s])*kabu
    

print(ans)

Solution (Python):
n=int(input())
a=list(map(int,input().split()))
m=1000
k=0
peak=-1
for i in range(n-1):
    if a[i]<a[i+1]:
        peak=i+1

for i in range(peak):
    if a[i+1]>a[i] and k==0:
        k=m//a[i]
        m-=k*a[i]

    elif a[i+1]<a[i]:
        m+=k*a[i]
        k=0

if peak!=-1:
    m+=k*a[peak]
    k=0

print(m)

Solution (Python):
N = int(input())
stocks = list(map(int,input().split()))
now_stock = stocks[0]
cash = 1000
max_min_stocks = []
if now_stock <= stocks[1]:
    up_flag = True
    max_min_stocks.append(stocks[0])
else:
    up_flag = False
f_up_flag = up_flag
i = 1

while i < N:
    next_stock = stocks[i]
    if up_flag:
        if now_stock <= next_stock:
            now_stock = next_stock
        else:
            max_min_stocks.append(now_stock)
            up_flag = False
    else:
        if now_stock >= next_stock:
            now_stock = next_stock
        else:
            max_min_stocks.append(now_stock)
            up_flag = True
    now_stock = next_stock
    i += 1
if up_flag:
    max_min_stocks.append(stocks[-1])
else:
    max_min_stocks.append(stocks[-1])


if len(max_min_stocks) >= 2:
    for i in range(len(max_min_stocks) // 2):
        hold_stocks = cash // max_min_stocks[2 * i]
        cash -= hold_stocks * max_min_stocks[2 * i]
        cash += hold_stocks * max_min_stocks[2 * i + 1]
print(cash)

Solution (Python):
N=int(input())
A= list(map(int,input().split()))
kabu=0
kane=1000
kabukin=0
for a in range(N-1):
    if A[a]<A[a+1] and kane>A[a]:
        
            kabu=int(kane/A[a])
            kabukin=kabu*A[a]
            kane=kane-kabu*A[a]
    elif A[a]>A[a+1] and kabu>=1:
        kane=kane+kabu*A[a]
        kabu=0

if kabu>0:
    kane+=kabu*A[-1]
print(kane)

Solution (Python):
import sys












stdin = sys.stdin
sys.setrecursionlimit(10 ** 7)
MIN = -10 ** 9
MOD = 10 ** 9 + 7
INF = float("inf")
IINF = 10 ** 18

def solve():
    n = int(stdin.readline().rstrip())
    A = list(map(int, stdin.readline().rstrip().split()))
    
    
    
    
    money = 1000
    kabu = 0
    down = 0
    up = 0
    kijun = A[0]
    for i in range(1,n):
        a = A[i]
        if i == 1:
            if kijun < a:
                buy = kijun
                katta = money//buy
                kabu += katta
                money -= katta*buy
                down = 0
                up = 1
                kijun = a
            elif kijun > a:
                down = 1
                kijun = a
        if up == 1:
            if kijun > a:
                sell = kijun
                money += sell * kabu
                kabu = 0
                up = 0
                down = 1
                kijun = a
            else:
                kijun = a
        elif down == 1:
            if kijun < a:
                buy = kijun
                katta = money//buy
                kabu += katta
                money -= katta*buy
                down = 0
                up = 1
                kijun = a
            else:
                kijun = a
        else:
            if kijun < a:
                buy = kijun
                katta = money//buy
                kabu += katta
                money -= katta*buy
                down = 0
                up = 1
                kijun = a
            elif kijun > a:
                sell = kijun
                money += sell * kabu
                kabu = 0
                up = 0
                down = 1
                kijun = a
    if kabu > 0:
        money += kabu * A[-1]
    print(money)




if __name__ == '__main__':
    solve()

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

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

res = 1000
flag = False
kabu = 0
for i in range(n):
    if buysold[i] == 0 and not flag:
        kabu = res // a[i]
        res -= kabu*a[i]
        flag = True
    if buysold[i] == 1 and flag:
        res += kabu*a[i]
        kabu = 0
        flag = False

if buysold[n-1] == 0:
    res += kabu*a[n-1]
print(res)

Solution (Python):

def main():
    N = int(input())
    A = [int(x) for x in input().split(" ")]
    cash = 1000
    stock = 0
    for i in range(N-1):
        if A[i] < A[i+1]:
            stock += cash // A[i]
            cash = cash % A[i]
        elif stock != 0 and A[i] > A[i+1]:
            cash = cash + A[i]*stock
            stock = 0
    print(cash + A[-1]*stock)


if __name__ == '__main__':
    main()

Solution (Python):
N=int(input())
A=list(map(int,input().split()))
a=0
c=1000
for i in range(N-1):
  if A[i]<A[i+1] and a==0:
    a,c=divmod(c,A[i])
    sb="False"
  elif A[i]>A[i+1] and a>0:
    c+=a*A[i]
    a=0

print(a*A[-1]+c)

Solution (Python):
def main():
    n = int(input())
    a = list(map(int, input().split()))
    small = [a[0]]
    diff = 1  
    for i in range(1, n):
        if (a[i] < a[i - 1] and diff == 1) or (a[i] > a[i - 1] and diff == 0):
            small.append(a[i - 1])
            diff += 1
            diff %= 2
    small.append(a[-1])
    ans = 1000
    stock = 0
    for i, s in enumerate(small):
        if i % 2 == 0:
            stock += ans // s
            ans %= s
        else:
            ans += s * stock
            stock = 0
    if stock > 0:
        ans += stock * small[-1]
    print(max(1000, ans))


if __name__ == '__main__':
    main()

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

Solution (Python):
def resolve():
    n = int(input())
    a = list(map(int, input().split()))
    ans = 1000
    pm = 1
    for i in range(n-1):
        if a[i] < a[i+1]:
            t = ans // a[i]
            ans += t * (a[i+1] - a[i])

    print(ans)


if __name__ == "__main__":
    resolve()

Solution (Python):
import os
import heapq
import sys
import math
import bisect
import operator
from collections import defaultdict
from io import BytesIO, IOBase
def gcd(a,b):
    if b==0:

        return a
    else:
        return gcd(b,a%b)
def power(x, p,m):
    res = 1
    while p:
        if p & 1:
            res = (res * x) % m
        x = (x * x) % m
        p >>= 1
    return res
def inar():
    return [int(k) for k in input().split()]









def lcm(num1,num2):
    return (num1*num2)//gcd(num1,num2)

def main():
    
    n=int(input())
    arr=inar()
    mn=arr[0]
    mx=arr[0]
    take=1000
    for i in range(1,n):
        if arr[i]<mx:
            got=take//mn
            rem=take%mn
            take=got*mx
            take+=rem
            mx=arr[i]
            mn=arr[i]
        else:
            mx=max(arr[i],mx)
    got = take // mn
    rem = take % mn
    take = got * mx
    take += rem
    print(take)














BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")

if __name__ == "__main__":
    main()

Solution (Python):
from bisect import bisect_right

def main():
    N = int(input())
    A = list(map(int, input().split()))
    INF = 10 ** 18
    last_max = A[0]
    last_min = A[0]

    money = 1000
    stock = 0
    old_trend = 0
    trend = A[1] - A[0]
    buy_point = []
    bought_point = []

    for i in range(N-1):
        trend = A[i+1] - A[i]
        if trend * old_trend > 0 or trend == 0:
            continue
        else:
            if trend > 0:
                buy_point.append(i)
            if trend < 0:
                bought_point.append(i)
        old_trend = trend

    if len(buy_point) > len(bought_point):
        bought_point.append(N-1)

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

            nx_bought_idx = bisect_right(bought_point,i)
            bought_value = A[nx_bought_idx]
            j = i - 1
            while j >= 0 and money >= 100:
                if A[j] < bought_value and money >= A[i]:
                    money -= A[j]
                    stock += 1
                    break
                j -= 1
        
        if i in bought_point:
            bought = stock
            stock = 0
            money += bought * A[i]
    print(money)
    


if __name__ == "__main__":
    main()

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

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

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

money = 1000


for i in range(1, n):
  p_now = arr[i]
  p_before = arr[i-1]
  if p_before < p_now:
    stock = money // p_before
    money += stock*(p_now - p_before)

print(money)

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

count = 0
set = [a[0]]

for i in range(n-1):
    if a[i] >= a[i+1]:
        count += 1
if count == n-1:
    print(1000)
    exit()

for i in range(1,n):
    if a[i-1] != a[i]:
        set += [a[i]]


num = len(set)
seifu = 0

set2 = [set[0],set[1]]

if set[0] > set[1]:
    seifu = -1
else:
    seifu = 1

i_now = 1

for i in range(2,num):
    if set[i-1] < set[i] and seifu < 0:
        set2 += [set[i]]
        seifu = 1
        i_now += 1
    elif set[i-1] < set[i] and seifu > 0:
        set2[i_now] = set[i]
    elif set[i-1] > set[i] and seifu > 0:
        set2+= [set[i]]
        i_now += 1
        seifu = -1
    elif set[i-1] > set[i] and seifu < 0:
        set2[i_now] = set[i]


if set2[0] > set2[1]:
    set2 = set2[1:]

if len(set2)%2 != 0:
    set2 = set2[:len(set2)-1]



buy = 0
coin = 1000
num2 = 0

for i in range(len(set2)-1):
    if set2[i] < set2[i+1] and buy == 0:
        num2 = coin//set2[i]
        coin = coin - set2[i] * num2
        buy = 1

    elif set2[i] > set2[i+1] and buy == 1:
        coin = coin + num2 * set2[i]
        buy = 0


coin += num2*set2[len(set2)-1]

print(coin)

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

money=1000
stocks=0

for i in range(N): 
    if i==N-1:
        
        money+=(A[i]*stocks)
        stocks=0
    elif A[i+1]>A[i]:
        
        plus_stock,money=divmod(money,A[i])
        stocks+=plus_stock
    elif A[i+1]<A[i]:
        
        money+=(A[i]*stocks)
        stocks=0
print(money)

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

dp = [[[0]*2 for _ in range(2)] for _ in range(N)]

dp[0][0][0] = 1000
dp[0][1][0] = 1000%A[0]
dp[0][1][1] = 1000//A[0]

for i, a in enumerate(A):
  if i == 0:
    dp[0][0][0] = 1000
    dp[0][1][0] = 1000%a
    dp[0][1][1] = 1000//a
  else:
    if dp[i-1][0][0] < dp[i-1][1][0] + dp[i-1][1][1]*a:
      dp[i][0][0] = dp[i-1][1][0] + dp[i-1][1][1]*a
    else:
      dp[i][0][0] = dp[i-1][0][0]
    if dp[i-1][1][1] < dp[i][0][0]//a or dp[i-1][1][1] == dp[i][0][0]//a and dp[i-1][1][0] < dp[i][0][0]%a:
      dp[i][1][0] = dp[i][0][0]%a
      dp[i][1][1] = dp[i][0][0]//a
    else:
      dp[i][1][0] = dp[i-1][1][0]
      dp[i][1][1] = dp[i-1][1][1]
if dp[N-1][0][0] < dp[N-1][1][0] + dp[N-1][1][1]*A[N-1]:
  print(dp[N-1][1][0] + dp[N-1][1][1]*A[N-1])
else:
  print(dp[N-1][0][0])

Solution (Python):
import numpy as np
import copy

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


trigger = 0

As_seiri = []

tmp = 0
for i in range(N-1):
    if(As[i] < As[i+1] and trigger == 0):
        As_seiri.append(As[i])
        trigger = 1
        continue

    elif(As[i] > As[i+1] and trigger == 1):
        As_seiri.append(As[i])
        trigger = 0
        continue



if(len(As_seiri) == 0):
    print("1000")
    exit()


money = 1000
kabu = 0

for A in As_seiri:
    if(kabu == 0):
        kabu = money // A
        money = money - kabu * A
    
    else:
        money = money + (kabu * A)
        kabu = 0

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

Solution (Python):

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

atm = 1000

for i in range(N-1):
    kb = 0
    if a[i+1] > a[i]:
        kb = atm//a[i]
        atm -= a[i]*kb
        atm += a[i+1]*kb
    elif a[i+1] < a[i]:
        pass

print(atm)

Solution (Python):
n=int(input())
inp = list(map(int,input().split()))
ini=(0,1000)
now=(0,1000)
m=inp[0]
now=(1000//m,1000%m)
flag=0
for i in range(1,len(inp)):
    if inp[i]>m:
        ini=(0,now[0]*inp[i]+now[1])
        now=(ini[1]//inp[i],ini[1]%inp[i])
        m=inp[i]
    else:
        now=(ini[1]//inp[i],ini[1]%inp[i])
        m=inp[i]
print (ini[1])

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

yen = 1000

kabu = 0

for i in range(n-1):
    if a[i] < a[i+1]:
        kabu_today = yen // a[i]
        kabu += kabu_today
        yen = yen % a[i]
        
    else:
        yen += kabu * a[i]
        kabu = 0
    


yen += kabu * a[n-1]
kabu = 0

print(yen)

Solution (Python):
n=int(input())
l=[*map(int,input().split())]
a=1000
c=0
for i in range(n-1):
  if l[i]>l[i+1]:
    a+=c*l[i]
    c=0
  if l[i]<l[i+1]:
    while a>=l[i]:
      t=a//l[i]
      a-=t*l[i]
      c+=t
print(a+c*l[n-1])

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

i = 0
flag = True 
num_stock = 0
money = 1000
while i < n:
    
    if flag:
        while i + 1 < n and A[i] >= A[i + 1]:
            i += 1
        
        if i == n - 1:
            break
        num_stock = money // A[i]
        money -= num_stock * A[i]
        flag = False
    
    else:
        while i + 1 < n and A[i] <= A[i + 1]:
            i += 1
        money += num_stock * A[i]
        num_stock = 0
        flag = True
    i += 1

print(money)