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()))
money = 1000
kabu = 0
for i in range(N-1):
    if A[i]<A[i+1]:
        if money >= A[i]:
            kabu = money//A[i]
            money = money%A[i]
    elif A[i]>A[i+1]:
        if kabu > 0:
            money += kabu*A[i]
            kabu = 0
if kabu>0:
    money += kabu*A[-1]
print(max(money,1000))

Solution (Python):
import sys
import numpy as np

readline = sys.stdin.readline
read = sys.stdin.read

n = int(input())
a = np.array(readline().split(), dtype=np.int64)
a = np.insert(a, n, 0)
C = 1000
I = 0
for i in range(n):
    if a[i] < a[i+1]:
        x = C // a[i]
        I += x
        C -= x * a[i]
    if a[i] > a[i+1]:
        C += I * a[i]
        I = 0
print(C)

Solution (Python):
import math

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

Money=1000
Kabu=0

def MoneyWar(Money,Kabu,A,N):
  for i in range(N-1):
    if A[i]<A[i+1]:
      Kounyu=math.floor(Money/A[i])
      Money-=A[i]*Kounyu
      Kabu+=Kounyu

    if A[i]>A[i+1]:
      Money+=Kabu*A[i]
      Kabu=0

      
  if Kabu>0:
    Money+=Kabu*A[-1]
    
  return Money

print(MoneyWar(Money,Kabu,A,N))

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

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

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

m=1000
k=0
for i in range(n-1):
    if l[i]==1:
        p=m//a[i]
        k+=p
        m-=p*a[i]

    if l[i]==-1:
        m+=k*a[i]
        k=0

m+=k*a[n-1]
print(m)

Solution (Python):
n = int(input())
a = list(map(int,input().split()))
yen = 1000
kabu = 0

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

Solution (Python):
import collections
N=int(input())
A=list(map(int,input().split()))
i=0
A.insert(0,float("inf"))

buy=[0]*N
sell=[0]*N
for i in range(N-1):
    if (A[i]>=A[i+1])and(A[i+2]>=A[i+1]):
        buy[i]=1
    if (A[i]<=A[i+1])and(A[i+2]<=A[i+1]):
        sell[i]=1
kabu=0
money=1000


A=A[1:]

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

money=money+kabu*A[N-1]
print(money)

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

Solution (Python):
def main():
    n = int(input())
    a = tuple([int(t)for t in input().split()])

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

    ans+=stock*a[-1]
    stock = 0
    print(ans)
if __name__ == "__main__":
    main()

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

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

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



money = 1000
stock = 0

for i in range(N):
    if stock > 0 and i>=1:
        if A[i] > A[i-1]:
            money += stock * A[i]
            stock -= stock
    if money > A[i] and i<=N-2:
        if A[i]<A[i+1]:
            stock += money//A[i]
            money -= (money//A[i]) * A[i]

        
print(money)

Solution (Python):
n = int(input())
a = list(map(int,input().split()))
mo = 1000
now = True  
have = 0    
price = 0 
now_max = 0
now_min = 1000000000000
for i in range(n-1):
    if now:
        if a[i]<a[i+1]:
            have = int(mo/a[i])
            price = a[i]
            mo = mo-have*price
            now = not now
    else:
        if a[i]>a[i+1]:
            mo += have*a[i]
            heve = 0
            now = not now
if not now:
    mo += have*a[n-1]

print(mo)

Solution (Python):

"""
Created on Sat Jul 25 21:15:35 2020

@author: NEC-PCuser
"""

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

money = 1000
kabu = 0

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

if (kabu != 0):
    money += kabu * A[N - 1]

print(money)

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

now = 1000
stack = 0
price = a[0]
for i in range(1, n):
    
    if price > a[i]:
        
        if stack != 0:
            now += stack * price
            stack = 0
    
    else:
        
        if stack == 0:
            stack = now // price
            now -= stack * price
    price = a[i]

if stack != 0:
    now += stack * price
print(now)

Solution (Python):
n=int(input())
a=list(map(int,input().split()))
m=1000
bef=a[0]
up=[]
k=0
for i in a[1:]:
  if i>bef:
    up.append(1)
  else:
    up.append(0)
  bef=i
bef=up[0]
if bef:
  k=m//a[0]
  m=m%a[0]  

for i in range(1,n-1):
  if up[i]<bef:    
    m+=k*a[i]
    k=0
  elif up[i]>bef:
    k=m//a[i]
    m=m%a[i]
  bef=up[i]
m+=k*a[-1]
print(m)

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

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

main()

Solution (Python):


'''
Author: andyli
Time: 2020-07-25 19:57:02
'''

import os
from io import BytesIO, IOBase
import sys


def main():
    n = int(input())
    A = list(map(int, input().split()))

    a, b, p = 1000, 0, 0
    while p+1 < n and A[p] >= A[p+1]:
        p += 1
    while p < n-1:
        t = a//A[p]
        b += t
        a -= t*A[p]
        while p+1 < n and A[p] <= A[p+1]:
            p += 1
        a += b*A[p]
        b = 0
        if p == n:
            break
        while p+1 < n and A[p] >= A[p+1]:
            p += 1
    print(a)
    return



BUFSIZE = 1048576


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)
def input(): return sys.stdin.readline().rstrip('\r\n')




if __name__ == '__main__':
    main()

Solution (Python):
n=int(input())
a_list=list(map(int,input().split()))
current=1000
kabu=0
for i in range(n-1) :
  if a_list[i]<a_list[i+1] :
    kabu+=current//a_list[i]
    current=current%a_list[i]
    current += a_list[i+1] * kabu
    kabu = 0




print(current)

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

m = 1000
k = 0

for i in range(n):
    
    if i == n - 1:
        m += k * a[i]
        break

    
    if a[i] < a[i + 1]:
        k += m // a[i]
        m = m % a[i]
        continue
    
    
    if a[i] > a[i + 1]:
        m += k * a[i]
        k = 0
        continue

print(m)

Solution (Python):
N = int(input())
A = list(map(int, input().split()))
acd = A[0] <= A[1]
lst = [A[0]]
i = 1
while i < N:
    if acd:
        if A[i-1] > A[i]:
            lst.append(A[i-1])
            acd = 0
    else:
        if A[i-1] < A[i]:
            lst.append(A[i-1])
            acd = 1
    i += 1
if A[N-2] <= A[N-1]:
    lst.append(A[N-1])
if len(lst) == 1:
    print(1000)
    exit()
if lst[0] > lst[1]:
    lst = lst[1:]
if len(lst) < 2:
    X = 1000
else:
    X = 1000
    for i in range(0, len(lst), 2):
        c = X//lst[i]
        X -= c*lst[i]
        X += c*lst[i+1]
print(X)

Solution (Python):
n = int(input())
a = list(map(int,input().split()))
money = 1000
p = 0
def buy(m,a):
    global money
    global p
    num = m // a
    money -= num*a
    p += num
def sell(s,a):
    global money
    global p
    money += s*a
    p = 0
if a[0] <= a[1]:
    dx = 1
else:
    dx = -1
if dx == 1:
    buy(1000,a[0])
for i in range(n-2):
    if a[i+1] < a[i+2]:
        dy = 1
    elif a[i+1] == a[i+2]:
        dy = 0
    else:
        dy = -1
    if dx == 1 and dy == -1:
        sell(p,a[i+1])
    elif dx == -1 and dy == 1:
        buy(money,a[i+1])
    if dy != 0:
        dx = dy
sell(p,a[n-1])
print(money)

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

if A[0] < A[1]:
    kabu += money // A[0]
    money = money % A[0]

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

money += kabu * A[N-1]
kabu = 0
print(money)

Solution (Python):
INF = 10 ** 10

def solve(ns):
    n = len(ns)
    dp = [ set([(1000, 0)]), set([]) ]
    p = 0
    for price in ns:
        q = p ^ 1
        dp[q] = set()
        for (money, stock) in dp[p]:
            m1 = money + stock * price
            dp[q].add((m1, 0))
            m2 = money % price
            s2 = stock + money / price
            dp[q].add((m2, s2))
            dp[q].add((money, stock))
        p = q
    maxi = -INF
    for (money, stock) in dp[p]:
        maxi = max(maxi, money)
    return maxi

def solve2(ns):
    n = len(ns)
    dp = [1000] + [-INF for i in xrange(n)]
    for i in xrange(1, n + 1):
        for j in xrange(i + 1, n + 1):
            if ns[j - 1] <= ns[i - 1]:
                continue
            money = dp[i - 1]

            
            stock = money / ns[i - 1]
            money = money % ns[i - 1]

            
            money = money + stock * ns[j - 1]
            stock = 0

            dp[j] = max(dp[j], money)
        dp[i] = max(dp[i], dp[i - 1])
    return max(dp)

assert solve2([200, 188, 181, 115, 160]) == 1360
assert solve2([200, 180, 160, 140, 120, 100]) == 1000
assert solve2([100, 130, 130, 130, 115, 115, 150]) == 1685

assert solve2([157, 193]) == 1216

n = int(raw_input())
ns = map(int, raw_input().split())


print solve2(ns[:])

Solution (Python):
N = int(input())
A = [int(i) for i in input().split()]
UD = []
last_idx = 0
for n in range(N-1):
    if A[n] < A[n+1]:
        UD.append('Up')
        last_idx = n
    else:
        UD.append('Down')
M = 1000
S = 0
for n in range(N-1):
    if UD[n] == 'Up':
        num = M//A[n]
        S += num
        M -= num*A[n]
    else:
        num = S*A[n]
        S = 0
        M += num
num = S*A[N-1]
S = 0
M += num
print(M)

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



N = int(input())
A = [int(x) for x in input().split()]

premin = A[0]
cur = 1000
for i in range(1, N):
    if A[i] > premin:
        cur = cur + (cur//premin)*(A[i]-premin)
        premin = A[i]
    premin = min(premin, A[i])

print(cur)

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

money = 1000
kabu = 0

for i in range(N):
    if kabu == 0:
        flag = True
        for j in range(i+1, N):
            if A[i] > A[j]:
                flag = False
                break
            elif A[i] < A[j]:
                flag = True
                break
        else:
            flag = False
        if flag:
            buy = money // A[i]
            money -= buy * A[i]
            kabu += buy
    else:
        flag = True
        for j in range(i+1, N):
            if A[i] < A[j]:
                flag = False
                break
            elif A[i] > A[j]:
                flag = True
                break
        if flag:
            money += kabu * A[i]
            kabu = 0
    

print(money)

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


money_high = 1000
kabu_high = money_high // A[0]
zankin = 0
for i in range(n):
    money_high = max(kabu_high * A[i] + zankin, money_high)
    kabu_high = max(money_high // A[i], kabu_high)
    zankin = money_high % A[i]

print(max(kabu_high * A[n-1] + zankin, money_high))

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

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


dp = defaultdict(int)
dp[0] = 1000
for a in A:
    key, val = zip(*dp.items())
    for k, v in zip(key, val):
        
        dp[0] = max(dp[0], v + k * a)
        
        buy = v // a
        dp[k + buy] = max(dp[k + buy], v - buy * a)

print(dp[0])

Solution (Python):
def resolve():
    n = int(input())
    A = list(map(int, input().split()))
    funds = 1000
    stock = 0

    for i in range(n):
        if i > 0 and A[i] > A[i-1]:
            
            funds += A[i] * stock
            stock = 0
        if i < n-1 and A[i] < A[i+1]:
            
            stock += funds // A[i]
            funds -= A[i] * stock

    print(funds)

resolve()

Solution (Python):
n = int(input())
ls = list(map(int,input().split()))
ans = 1000

A = [ls[0]]

for i in range(1,n-1):
  if ls[i-1]<ls[i]<ls[i+1]:
    continue
  if ls[i-1]>ls[i]>ls[i+1]:
    continue
  if ls[i]==ls[i-1]:
    continue
    
  A.append(ls[i])
  
if A[-1] != ls[-1]:
  A.append(ls[-1])

for i in range(1,len(A)):
  if A[i-1]< A[i]:
    ans = ans%A[i-1] + ans//A[i-1]*A[i]
    
print(ans)

Solution (Python):
from collections import deque
n = int(input())
a = list(map(int,input().split()))
dp = [1000 for i in range(n)]

for i in range(n-1):
    for j in range(i,n):
        if a[i] < a[j]:
            mouke = dp[i] + (dp[i]//a[i])*(a[j]-a[i])
            dp[j] = max(dp[j],mouke)
        if j != 0:
            dp[j] = max(dp[j],dp[j-1])
print(dp[-1])

Solution (Python):
import math
import sys
import collections
import bisect
readline = sys.stdin.readline


def main():
    n = int(readline().rstrip())
    A = list(map(int, readline().rstrip().split()))
    sumA = 0
    money = 1000
    for i in range(n - 1):
        if A[i + 1] - A[i] > 0:
            money += (A[i + 1] - A[i]) * math.floor(money / A[i])
    print(money)


if __name__ == '__main__':
    main()

Solution (Python):
n = int(input())
a = list(map(int, input().split()))
a.append(0)
ans = 1000
mx = -1
mn = -1
i = n-1
for j in range(n-1):
    if a[j]<a[j+1]:
        mn = a[j]
        i = j
        break
dec = False
if(i==n-1):
    dec = True
while i<n:
    if not dec and a[i]>a[i+1]:
        mx = a[i]
        dec = True
        ans += (mx-mn)*(ans//mn)
    if dec and a[i]<a[i+1]:
        mn = a[i]
        dec = False
    i+=1
        
print(ans)

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

okane = 1000
kabu = 0
syozi=False

for i in range(n):
    if syozi:
        if i == n-1:
            okane = okane + a[i]*kabu
            break
        if a[i+1] >= a[i]:
            continue
        else:
            okane = okane + a[i]*kabu
            kabu = 0
            syozi = False
    else:
        if i == n-1:
            break
        if a[i+1] <= a[i]:
            continue
        else:
            kabu = okane//a[i]
            okane = okane - kabu*a[i]
            syozi = True

print(okane)

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

money = 1000
stocks = 0
up_flag = False

for i in range(n-1):
    if a[i] < a[i+1] and not up_flag:
        stocks += money//a[i]
        money -= stocks*a[i]
        up_flag = True
    elif a[i] > a[i+1] and up_flag:
        money += stocks*a[i]
        stocks = 0
        up_flag = False

if stocks>0:
    money += stocks*a[-1]

print(money)

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

sum=1000
have=0

for i in range(n-1):
    if have==0:
        if a[i]<a[i+1]:
            mai=sum//a[i]
            buy=mai*a[i]
            sum=sum-buy
            have=1
        if a[i]>a[i+1]:
            continue
        if a[i]==a[i+1]:
            continue
    
    if have==1:
        if a[i]<a[i+1]:
            continue
        if a[i]>a[i+1]:
            sum=sum+a[i]*mai
            have=0
            continue
        if a[i]==a[i+1]:
            continue


if have==1:
    sum=sum+mai*a[n-1]

print(sum)

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

stock_dp = [[0, 0] for _ in range(n+1)]
value_dp = [0] * (n + 1)

value_dp[0] = 1000
for i in range(1, n + 1):
    x = value_dp[i - 1]
    y = stock_dp[i - 1][0] + stock_dp[i - 1][1] * a[i - 1]
    if x > y:
        value_dp[i] = x
    else:
        value_dp[i] = y
    x = value_dp[i - 1] // a[i - 1] 
    y = stock_dp[i - 1][0] // a[i - 1] + stock_dp[i - 1][1]
    rx = value_dp[i - 1] % a[i - 1]
    ry = stock_dp[i - 1][0] % a[i - 1]
    if x > y:
        stock_dp[i][0] = rx
        stock_dp[i][1] = x
    elif x < y:
        stock_dp[i][0] = ry
        stock_dp[i][1] = y
    else:
        stock_dp[i][0] = max(rx, ry)
        stock_dp[i][1] = x
print(value_dp[n])

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

prev_direction = 0
money = 1000
stock = 0
for i, current in enumerate(values):
    if i == 0:
        continue

    yesterday = values[i - 1]
    
    if current - yesterday > 0:
        if prev_direction != 1:
            
            stockNum = money // yesterday
            buy = stockNum * yesterday
            money -= buy
            stock = stockNum
        prev_direction = 1

    elif current - yesterday < 0:
        
        if prev_direction != -1:
            sell = yesterday * stock
            stock = 0
            money += sell
        prev_direction = -1

    else:
        continue

lastSell = stock * values[len(values) - 1]
money += lastSell

print(money)

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

L = [0 for _ in range(N)] 
for i in range(N):
  if i == 0:
    if A[i+1] >= A[i]:
      L[i] = -1
    else:
      L[i] = 1
  elif i == N-1:
    if A[i] >= A[i-1]:
      L[i] = 1
    else:
      L[i] = -1
  else:
    if A[i] >= A[i-1] and A[i] >= A[i+1]:
      L[i] = 1
    elif A[i] <= A[i-1] and A[i] <= A[i+1]:
      L[i] = -1

kabu = 0
for i in range(N):
  
  if L[i] == 1:
    
    money += kabu*A[i]
    kabu = 0
  elif L[i] == -1:
    
    uri = money//A[i]
    money -= uri*A[i]
    kabu += uri
  
ans = money+kabu*A[-1]
print(ans)

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

joutai = "nasi"
m = 1000
k = 0

for i in range(n-1):
    if joutai == "nasi":
        if a[i] < a[i+1]:
            k = m // a[i]
            m -= k * a[i]
            joutai = "ari"
    else:
        if a[i] > a[i+1]:
            m += k * a[i]
            k = 0
            joutai = "nasi"

m += k * a[n-1]

print(m)

Solution (Python):
import sys
sys.setrecursionlimit(10**6)


def main(input, print):
    N = int(input())
    A = list(map(int, input().split()))
    ans = 1000
    i = 0
    while i < N:
        now = A[i]
        max = now
        next = i
        for j in range(i+1, N):
            if A[j-1] > A[j]:
                break
            if max < A[j]:
                max = A[j]
                next = j
        if now < max:
            cnt = ans // now
            ans += max * cnt - now * cnt
        i = next+1
    print(ans)


if __name__ == '__main__':
    main(sys.stdin.readline, print)

Solution (Python):






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


jpy = 1000
stocks = 0

for i in range(N):
    
    if i == N - 1:
        jpy += prices[i] * stocks
        stocks = 0
        break
    
    
    if prices[i+1] > prices[i]:
        stocks += jpy // prices[i]
        jpy = jpy % prices[i]
    
    elif prices[i+1] < prices[i]:
        jpy += prices[i] * stocks
        stocks = 0
    
    else:
        pass
print(jpy)

Solution (Python):
def main():
    N = int(input())
    *A, = map(int, input().split())

    money = 1000

    low = A[0]
    high = -1
    for x in A:
        if high < x:
            high = x
            continue

        if high > x:
            money += (high - low) * (money // low)
            low = high = x

    money += max(0, high - low) * (money // low)

    print(money)


if __name__ == '__main__':
    main()

Solution (Python):
n=int(input())
a=[]

for i in input().split():
    a.append(int(i))
p=1000
for i in range(1,n):
    if(a[i]>a[i-1]):
        p=((p//a[i-1])*a[i])+(p%a[i-1])
print(p)

Solution (Python):


import sys
import numpy as np
int1 = lambda x: int(x) - 1
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)


def list_split(l):
    res = []
    idx = 0
    for i in range(len(l) - 1):
        if l[i] > l[i + 1]:
            res.append(l[idx:i + 1])
            idx = i + 1

    res.append(l[idx:len(l)])

    return res


N, *A = map(int, read().split())
money = 1_000
n_stocks = 0
cost = 0

ll = list_split(A)

for l in ll:
    if len(l) == 1:
        continue
    acc = money // min(l)
    money -= acc * min(l)
    money += acc * max(l)

print(money)

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

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




def RD(): return sys.stdin.read()
def II(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))


def main():
	n=II()
	A=LI()
	A.append(0)

	L=[]
	R=[]

	f=0
	now=200
	i=0
	while i<n+1:
		if f==0:
			if A[i]<=now:
				now=A[i]
				i+=1
			else:
				L.append(now)
				f=1
		else:
			if A[i]>=now:
				now=A[i]
				i+=1
			else:
				R.append(now)
				f=0

	

	ans=1000

	for i,j in zip(L,R):
		q,r=divmod(ans,i)
		ans=q*j+r
	print(ans)





















if __name__ == "__main__":
	main()

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

ans = 1000

KAI = -1
URI = 1
phase = KAI

kabu_min = a[0]
kabu_max = -1

for i in range(1, n):
  if phase == KAI and a[i] <= kabu_min:
    kabu_min = a[i]
  elif phase == KAI:
    kabu_max = a[i]
    phase = URI
  elif phase == URI and a[i] >= kabu_max:
    kabu_max = a[i]
  elif phase == URI:
    ans = (ans % kabu_min) + (ans // kabu_min) * kabu_max
    kabu_min = a[i]
    kabu_max = -1
    phase = KAI

if phase == URI and kabu_max > kabu_min:
  ans = (ans % kabu_min) + (ans // kabu_min) * kabu_max

print(ans)

Solution (Python):


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

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

print(P)

Solution (Python):
import sys

input = sys.stdin.readline


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

    ans = 1000
    ll = rr = A[0]
    status = "down"
    for a in A[1:]:
        if status == "down":
            if ll < a:
                status = "up"
                rr = a
            else:
                ll = a
        else:
            if rr <= a:
                rr = a
            else:
                status = "down"
                q, r = divmod(ans, ll)
                ans = rr * q + r
                ll = a

    if status == "up":
        q, r = divmod(ans, ll)
        ans = rr * q + r

    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
n = int(input())
money = 1000
beet = 0
a = [int(i) for i in input().split()]

def buy(price):
    global money
    global beet
    beet = money // price
    money = money % price

def sell(price):
    global money
    global beet
    money += beet * price
    beet = 0

flag = True
for i in range(n-1):
    if flag:
        buy(a[i])
        flag = False
    if a[i] > a[i+1]:
        sell(a[i])
        flag = True
sell(a[-1])
print(money)

Solution (Python):
def main():
    import sys
    sys.setrecursionlimit(10**6)
    input = sys.stdin.readline
    N = int(input())
    A = [int(x) for x in input().strip().split()]
    i = 0
    stock = 0
    cash = 1000
    while i+1 < N:
        if A[i] < A[i+1] and stock == 0:
            stock += cash // A[i]
            cash -= stock * A[i]
            
        elif A[i] > A[i+1]:
            cash += stock * A[i]
            
            stock = 0
        i += 1
    else:
        cash += stock * A[-1]
        
    print(cash)

if __name__ == '__main__':
    main()

Solution (Python):
N,*A = map(int, open(0).read().split())
init = A[0]
cash = 1000
stock = 0
if A[1] <= A[0]:
    dif = -1
else:
    stock,cash = divmod(cash,A[0])
    dif = 1
for i in range(2,N):
    if A[i] > A[i-1]:
        if dif == -1:
            stock,cash = divmod(cash,A[i-1])
            dif = 1
    elif A[i] < A[i-1]:
        if dif == 1:
            cash = cash + stock * A[i-1]
            stock = 0
            dif = -1
if dif == 1:
    cash = cash + stock * A[N-1]
print(cash)

Solution (Python):
def main():
    n = int(input())
    a = list(map(int,input().split()))
    init = 1000
    pinit = a[0]
    pprev = a[0]
    for i in range(1,len(a)):
        if(pprev > a[i]):
            c = init//pinit
            init -= c * pinit
            init += c*pprev
            pinit = a[i]
        pprev = a[i]
    if(pinit < a[n-1]):
        c = init//pinit
        init += c*(a[n-1] - pinit)
    print(init)
    return

if __name__=="__main__":
    main()

Solution (Python):
n = int(input())
dat = list(map(int, input().split()))
minval = maxval = dat[0]
kabu = 0
okane = 1000
prevval = dat[0]
for i in range(n):
    curval = dat[i]
    
    if curval == prevval:
        prevval = curval
        continue
    if curval > prevval:
        prevval = curval
        continue
    
    kabu = okane // minval
    okane -= (minval * kabu)
    
    okane += (prevval * kabu)
    
    minval = curval
    maxval = prevval
    prevval = curval


curval = dat[n-1]


if curval > minval:
    kabu = okane // minval
    okane -= (minval * kabu)
    
    okane += (curval * kabu)
    

print(okane)

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

ud = [0]

if A[1] > A[0]:
    trend = 1
elif A[1] == A[0]:
    trend = 0
else:
    trend = -1

if trend != 0:
    first_trend = trend
else:
    first_trend = 0
for i in range(1,N):
    if A[i] > A[i-1]:
        if first_trend==0:
            first_trend = 1
        if trend==-1:
            ud.append(i-1)
        trend = 1
    elif A[i] < A[i-1]:
        if first_trend==0:
            first_trend = -1
        if trend==1:
            ud.append(i-1)
        trend = -1

ud.append(N-1)

M = 1000

for i in range(len(ud)):
    if first_trend == 1:
        if i%2==0 and i!=len(ud)-1:
            stock = M // A[ud[i]]
            M = stock*A[ud[i+1]] + M % A[ud[i]]
    else:
        if i%2==1 and i!=len(ud)-1:
            stock = M // A[ud[i]]
            M = stock*A[ud[i+1]] + M % A[ud[i]]


print(M)