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()))
flag = 0 
money = 1000
stock = 0

for k in range(len(a)-1):
    
    if flag == 0:
        if a[k] < a[k+1]:
            stock = int(money / a[k])
            money = money - (a[k] * stock)
            flag = 1

    else:
        if a[k] > a[k+1]:
            money += stock * a[k]
            stock = 0
            flag = 0

k += 1
if flag == 1:
    money += stock * a[k]

print(money)

Solution (Python):
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): 
	return list(map(int,input().split()))
def m(): 
	return map(int,input().split())
def onem(): 
	return int(input())
def s(x): 
	a = []
	if len(x) == 0:
		return []
	aa = x[0]
	su = 1
	for i in range(len(x)-1):
		if aa != x[i+1]:
			a.append([aa,su])
			aa = x[i+1]
			su = 1
		else:
			su += 1
	a.append([aa,su])
	return a
def jo(x): 
	return " ".join(map(str,x))
def max2(x): 
	return max(map(max,x))
def In(x,a): 
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False

def pow_k(x, n):
    ans = 1
    while n:
        if n % 2:
            ans *= x
        x *= x
        n >>= 1
    return ans

"""
def nibu(x,n,r):
	ll = 0
	rr = r
	while True:
		mid = (ll+rr)//2

	if rr == mid:
		return ll
	if (ここに評価入れる):
		rr = mid
	else:
		ll = mid+1
"""

n = onem()

a = l()


dp = [[0,0] for i in range(n)]

den = [0 for i in range(n)]

for i in range(n-2,-1,-1):
	if a[i] > a[i-1]:
		den[i-1] = 1
	else:
		break

po = [0 for i in range(n)]

for i in range(1,n):
	if a[i] < a[i-1]:
		po[i] = po[i-1]+1
	else:
		po[i] = po[i-1] 

now = a[0]
st = 0
for i in range(n):
	for j in range(i+1,n):
		if a[j] >= a[j-1]:
			1
		else:
			dp[i][0] = j-1
			break
	else:
		dp[i][0] = j
	for j in range(i+1,n):
		if a[j] <= a[j-1]:
			1
		else:
			dp[i][1] = j-1
			break
	else:
		dp[i][1] = j

lb = 0
hav = 0
mo = 1000

for i in range(n):
	if dp[i][0] == i:
		mo += hav * a[i]
		hav = 0
	if dp[i][1] == i:
		hav += mo // a[i]
		mo %= a[i]
		lb = a[i]
print(mo + lb * hav)

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

dp=[[0,0] for i in range(n)]
b=300
c=0
y=1000
for i in range(0,n-1):
  if a[i]>b:
    j=i+1
    by=0
    while j<n:
      if a[j]<a[i]:
        by=1
        break
      elif a[j]>a[i]:
        break
      j+=1
    if by==1:
      y+=c*a[i]
      c=0
      b=a[i]
  elif a[i]<b and c==0:
    j=i+1
    by=0
    while j<n:
      if a[j]>a[i]:
        by=1
        break
      elif a[j]<a[i]:
        break
      j+=1
  
    if by==1:
      c+=(y//a[i])
      y-=(y//a[i])*a[i]
      
      b=a[i]
print(y+c*a[n-1])

Solution (Python):
n=int(input())
a=list(map(int,input().split()))
stock,bill=0,1000
i=0
while i<n:
    if a[i]<=a[i+1]:
        t=i
        while i<n-1 and a[i]<=a[i+1]: i+=1
        temp=bill//a[t]
        stock+=temp
        bill-=temp*a[t]
        if i==n-1:
            bill+=stock*a[n-1]
            print(bill)
            exit()
    elif a[i]>=a[i+1]:
        t=i
        while i<n-1 and a[i]>=a[i+1]: i+=1
        bill+=stock*a[t]
        stock=0
        if i==n-1:
            print(bill)
            exit()

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

check = ['0']

for i in range(N - 1):
    if data[i] < data[i + 1]:
        check.append("+")
    elif data[i] == data[i + 1]:
        check.append("0")
    else:
        check.append("-")
   
latest_buy = None
for i in range(N - 1):
    price = data[i]
    if check[i + 1] == "+":
        stock += money // price
        money -= price * (money // price)
        latest_buy = i
        
    if check[i + 1] == "-":
        money += price * stock
        stock = 0
        latest_buy = None

if latest_buy != None:
    print(stock * data[latest_buy + 1] + money)
else:
    print(money)

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

money = 1000
cnt = 0
flag = 0
for i in range(len(_A)):
    if flag == 0 or flag == -1: 
        if _A[i] == 1: 
            cnt += money // A[i]
            money -= (money // A[i]) * A[i] 
            flag = 1
    elif flag == 0 or flag == 1: 
        if _A[i] == -1:
            money += cnt * A[i]  
            cnt = 0
            flag = -1
    

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

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

Solution (Python):
import bisect, collections, copy, heapq, itertools, math, string, sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = float('inf')
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

def resolve():
    N = I()
    A = LI()

    m = 1000
    up = []
    for i in range(N - 1):
        if A[i] < A[i+1]:
            up.append((A[i], A[i+1]))

    for i in range(len(up)):
        l, h = up[i]
        m = m // l * h + m % l

    print(m)

if __name__ == '__main__':
    resolve()

Solution (Python):

import sys
sys.setrecursionlimit(10**8)
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return [LIST() for _ in range(n)]
def NSTR(n): return [input() for _ in range(n)]


INF = float("inf")
MOD = 10**9 + 7


def main():
    N = INT()
    A = LIST()

    
    s = 0
    curr = A[0]
    money = 1000
    for i in range(1, N):
        
        if curr <= A[i]:
            
            curr = A[i]
        else:
            
            n = money // A[s]   
            money -= n*A[s]
            money += curr * n
            s = i
            curr = A[s]
    if curr == A[N-1] and s != N-1:
        n = money // A[s]   
        money -= n*A[s]
        money += curr * n
    print(money)

    return


if __name__ == '__main__':
    main()

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

print(money+stock*a_list[n-1])

Solution (Python):



n = int(input())
a = list(map(int, input().split()))
mny = 1000
stc = 0

sa = set(a)
sizea = len(sa)
ssa = sorted(list(sa))


for i in range(n):
    imj = False
    ilj = False
    for j in range(i+1,n):
        if a[i] < a[j]:
            imj = True
        elif a[i] > a[j]:
            ilj = True
        if imj and ilj:
            break
    
    if mny >= a[i] and imj and a[i] < a[i+1]:
        stc += mny//a[i]
        mny = mny - (a[i] * (mny//a[i]))
    elif ilj and a[i] > a[i+1]:
        mny += stc * a[i]
        stc -= stc


mny += stc * a[len(a)-1]

print(mny)

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

cache = 1000
kabu = 0
for i in range(n):
    if i == n - 1:
        cache += kabu * a[i]
        kabu = 0
        break

    if cache > a[i] and a[i] < a[i + 1]:
        kabu = cache // a[i]
        cache = cache % a[i]

    if kabu > 0 and a[i] > a[i + 1]:
        cache += kabu * a[i]
        kabu = 0

print(cache)

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

print(money+stocks*L[-1])

Solution (Python):
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from functools import reduce
from bisect import bisect_left, insort_left
from heapq import heapify, heappush, heappop

INPUT = lambda: sys.stdin.readline().rstrip()
INT = lambda: int(INPUT())
MAP = lambda: map(int, INPUT().split())
S_MAP = lambda: map(str, INPUT().split())
LIST = lambda: list(map(int, INPUT().split()))
S_LIST = lambda: list(map(str, INPUT().split()))
ZIP = lambda: zip(*(MAP() for _ in range(n)))

sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7


def main():
    N = INT()
    A = LIST()

    flag = False
    num, money = 0, 1000
    for i in range(N-1):
        if flag:
            if A[i] > A[i+1]:
                flag = False
                money += num * A[i]
                num -= money // A[i]
        else:
            if A[i] < A[i+1]:
                flag = True
                num += money // A[i]
                money -= num * A[i]

    print(A[-1]*num + money)
            

if __name__ == '__main__':
    main()

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

money = 1000
stock = 0
day = 0


def buy_all(m, s, price):
    stock_n = m // price
    price_all = price * stock_n
    s += stock_n
    m -= price_all

    return m, s


def sell_all(m, s, price):
    price_all = price * s
    s = 0
    m += price_all

    return m, s


while day < n - 1:
    today, tomorrow = a[day], a[day + 1]

    if today > tomorrow:
        money, stock = sell_all(money, stock, today)
    elif today < tomorrow:
        money, stock = buy_all(money, stock, today)
    else:
        pass

    day += 1

money, stock = sell_all(money, stock, a[-1])

print(money)

Solution (Python):



def input_int():
    return int(input())



def int1(x):
    return int(x) - 1



def input_to_int_map():
    return map(int, input().split())



def input_to_int_tuple():
    return tuple(map(int, input().split()))



def input_to_int_tuple_minus1():
    return tuple(map(int1, input().split()))

def main():
    n = input_int()
    a_array = input_to_int_tuple()

    money = 1000
    buy = []

    for i, now_val in enumerate(a_array):
        next_val = 0
        if (i + 1) < len(a_array):
            next_val = a_array[i + 1]

        if now_val < next_val:
            cnt = money // now_val
            buy.append((now_val, cnt))
            money = money % now_val

        elif now_val > next_val:
            for val, cnt in buy:
                money += now_val * cnt
            buy = []

    print(money)


if __name__ == "__main__":
    main()

Solution (Python):
n = int(input())
a = list(map(int,input().split()))
v = []
before = 0
for i in a:
    if i!=before:v.append(i)
    before = i
money = 1000
stack = 0
if len(v) != 1:
    if v[0]<v[1]:
        buy_point = [1]
    else:
        buy_point = [0]
    for i in range(1,len(v)-1):
        if v[i-1]  < v[i] < v[i+1]:
            buy_point.append(2)
        elif v[i-1]  > v[i] > v[i+1]:
            buy_point.append(0)
        elif v[i-1]  < v[i] and v[i] > v[i+1]:
            buy_point.append(-1)
        elif v[i-1]  > v[i] and v[i] < v[i+1]:
            buy_point.append(1)
        else:
            print('error')
    if v[-2] < v[-1]:
        buy_point.append(-1)
    else:
        buy_point.append(0)

    for (i,j) in zip(v,buy_point):
        if j == 1:
            stack += money//i
            money = money%i
        elif j == -1:
            money += stack * i
            stack = 0
        elif j == 2:
            stack += money//i
            money = money%i

print(money)

Solution (Python):






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





def main():
    mylist = []
    s = 0
    m = 1000
    ans = m
    for i in range(1,N):
        if A[i] > A[i-1]:
            mylist.append(1)
        elif A[i] < A[i-1]:
            mylist.append(-1)
        else:
            mylist.append(0)
    for j,x in enumerate(mylist):
        if x > 0:
            b = m//A[j]
            s += b
            m -= b*A[j]
        elif x < 0:
            m += s*A[j]
            s = 0
        ans = max(ans, m+s*A[j])
    ans = max(ans, m+s*A[-1])
    print(ans)





if __name__ == '__main__':
    main()

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

money =1000
idx = 0
tmp_id = 0

while(idx < N-1):
    if(A[idx] <= A[idx+1]):
        idx += 1
        if(idx >= N-1):
            min_a = min(A[tmp_id:(idx+1)])
            max_a = max(A[tmp_id:(idx+1)])
            if(min_a == max_a):
                break
            n = money//min_a
            money = money - n*min_a
            money += max_a*n
            break 
    else:
        min_a = min(A[tmp_id:(idx+1)])
        max_a = max(A[tmp_id:(idx+1)])
        
        if(min_a == max_a):
            idx += 1
            tmp_id = idx
            continue
        n = money//min_a
        money = money - n*min_a
        money += max_a*n
        
        tmp = A[idx]
        idx += 1
        tmp_id = idx
print(money)

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

s = 1000
c = 0
upflg = 0
dwnflg = 0
for i in range(n-1):
  if a[i+1] > a[i]:
    dwnflg = 0
    if upflg == 1:
      continue
    c = s//a[i]
    s -= c*a[i]
    upflg = 1
  elif a[i+1] == a[i]:
    continue
  else:
    upflg = 0
    if dwnflg == 1:
      continue
    s += c*a[i]
    dwnflg = 1
  
if upflg == 1:
  s += c*a[-1]
print(max(s,1000))

Solution (Python):


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

A = [201] + A + [99]

money = 1000
stock = 0

sell_point = [0]*len(A)
buy_point = [0]*len(A)

position = "buy"

for i in range(len(A)-1):
    if position=="buy":
        if A[i] < A[i+1]:
            buy_point[i] = 1
            position ="sell"
            
            ba = money//A[i]
            
            money -= ba*A[i]
            stock += ba
            
    elif position=="sell":
        if A[i] > A[i+1]:
            sell_point[i] = 1
            position = "buy"
            
            sa = stock
            
            money += sa*A[i]
            stock = 0
print(money)

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

money = 1000
stock = 0

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

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

Solution (Python):
def resolve():
    n = int(input())
    a = list(map(int, input().split()))
    b = [0]*n
    for i in range(n-1):
        if a[i] < a[i+1]:
            b[i] = 1        
        elif a[i] > a[i+1]:
            b[i] = -1       
    c = [0]*n
    if b[0] == 1:
        c[0] = 1
    elif b[0] == -1:
        c[0] = -1
    for i in range(1,n-1):
        if (b[i-1]==0 or b[i-1]==-1) and b[i] == 1:       
            c[i] = 1       
        elif (b[i-1]==0 or b[i-1] ==1) and b[i] == -1:  
            c[i] = -1      
    kab = 0
    money = 1000
    for i in range(n):
        if c[i] == -1:
            money += kab*a[i]
            kab = 0
        elif c[i] == 1:
            kab += money//a[i]
            money %= a[i]
    money += kab*a[-1]
    print(money)
resolve()

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

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

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

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

dp = [0]*(N+1)
L1 = [[0]*2 for _ in range(N+1)]
L2 = [[0]*2 for _ in range(N+1)]
L1[0][0] = 1000

for i in range(N):
    for j in range(i+1):
        if L1[i+1][0] < L1[j][0]+L1[j][1]*A[i]:
            L1[i+1][0] = L1[j][0]+L1[j][1]*A[i]
            L1[i+1][1] = 0
        if L1[i+1][0] < L2[j][0]+L2[j][1]*A[i]:
            L1[i+1][0] = L2[j][0]+L2[j][1]*A[i]
            L1[i+1][1] = 0
        if L2[i+1][1] < L1[j][1]+L1[j][0]//A[i] or (L2[i+1][1] == L1[j][1]+L1[j][0]//A[i] and L2[i+1][0] < L1[j][0]%A[i]):
            L2[i+1][1] = L1[j][1]+L1[j][0]//A[i]
            L2[i+1][0] = L1[j][0]%A[i]
        if L2[i+1][1] < L2[j][1]+L2[j][0]//A[i] or (L2[i+1][1] == L2[j][1]+L2[j][0]//A[i] and L2[i+1][0] < L2[j][0]%A[i]):
            L2[i+1][1] = L2[j][1]+L2[j][0]//A[i]
            L2[i+1][0] = L2[j][0]%A[i]
    dp[i+1] = max(dp[i], L1[i+1][0]+L1[i+1][1]*A[i], L2[i+1][0]+L2[i+1][1]*A[i])

print(dp[-1])

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

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


b = 1000


p = 0
q = 0

for e in a:
    b = max(b,p + q*e)

    q += p//e
    p = p%e

    p2 = b%e
    q2 = b//e

    if q2 > q:
        q = q2
        p = p2
    elif q2 == q:
        p = max(p,p2)

print(b)

Solution (Python):
import sys

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


def main():
    n = int(readline())
    a = list(map(int, readline().split()))
    money = 1000
    stock = 0

    day = 0

    while day < n - 1:
        if stock == 0:
            cur = a[day]
            buy_day = day
            for i in range(day + 1, n):
                if cur >= a[i]:
                    cur = a[i]
                else:
                    buy_day = i - 1
                    break
            else:
                break
            stock += money // a[buy_day]
            money -= a[buy_day] * stock
            day = buy_day
        else:
            sell_day = 0
            cur = a[day]
            for i in range(day + 1, n):
                if cur <= a[i]:
                    cur = a[i]
                else:
                    sell_day = i - 1
                    break
            else:
                sell_day = n - 1
            money += a[sell_day] * stock
            stock = 0
            day = sell_day

    print(money)


if __name__ == '__main__':
    main()

Solution (Python):
import sys
N=int(input())
alist=list(map(int,input().split()))

a2list=[alist[0]]
for i in range(1,N):
  if a2list[-1]!=alist[i]:
    a2list.append(alist[i])


N2=len(a2list)
if N2==1:
  print(1000)
  sys.exit(0)

yama_list=[False]*N2
tani_list=[False]*N2
if a2list[0]>a2list[1]:
  yama_list[0]=True
if a2list[0]<a2list[1]:
  tani_list[0]=True

for i in range(1,N2-1):
  if a2list[i-1]<a2list[i]>a2list[i+1]:
    yama_list[i]=True
  if a2list[i-1]>a2list[i]<a2list[i+1]:
    tani_list[i]=True
    
if a2list[N2-2]<a2list[N2-1]:
  yama_list[N2-1]=True
if a2list[N2-2]>a2list[N2-1]:
  tani_list[N2-1]=True
    



money=1000
kabu=0
for i in range(N2):
  if yama_list[i]:
    
    money+=a2list[i]*kabu
    kabu=0
  if tani_list[i] and i<N2-1:
    
    k=money//a2list[i]
    kabu+=k
    money-=k*a2list[i]
    
print(money)

Solution (Python):

import sys, re
from collections import deque, defaultdict, Counter, OrderedDict
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from heapq import heappush, heappop, heapify, nlargest, nsmallest
def STR(): return list(input())
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def list2d(a, b, c): return [[c] * b for i in range(a)]
def sortListWithIndex(listOfTuples, idx):   return (sorted(listOfTuples, key=lambda x: x[idx]))
def sortDictWithVal(passedDic):
    temp = sorted(passedDic.items(), key=lambda kv: (kv[1], kv[0]))
    toret = {}
    for tup in temp:
        toret[tup[0]] = tup[1]
    return toret
def sortDictWithKey(passedDic):
    return dict(OrderedDict(sorted(passedDic.items())))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

n = INT()

a = LIST()

curr = 1000

st = 0

for i in range(1, n):
    if(a[i]>a[i-1]):
        if(curr>0):
            temp = curr//a[i-1]
            st+=temp
            curr-=temp*a[i-1]
    elif(a[i]<a[i-1]):
        if(st>0):
            curr+=st*a[i-1]
            st = 0

if(st>0):
    curr+=st*a[-1]
print(curr)

Solution (Python):
def solve():
  ans = 0
  N = int(input())
  A = [float('inf')]+list(map(int, input().split()))+[-float('inf')]
  updown = ['']*(N+1)
  updown[0] = 'down'
  for i in range(1,N+1):
    if A[i]>A[i+1]:
      updown[i] = 'down'
    elif A[i]<A[i+1]:
      updown[i] = 'up'
    else:
      updown[i] = updown[i-1]
  stock = 0
  money = 1000
  if 'up' not in updown:
    ind = -1
  else:
    ind = N-updown[::-1].index('up')
  for i in range(N):
    if updown[i]=='up' and updown[i+1]=='down':
      money += A[i+1]*stock
      stock = 0
      if i==ind:
        break
    elif updown[i]=='down' and updown[i+1]=='up':
      stock += money//A[i+1]
      money %= A[i+1]
  return money
print(solve())

Solution (Python):
n = int(input())
l = list(map(int,input().split()))
money = 1000
new_l = []
for i in range(n-1):
    if l[i] != l[i+1]:
        new_l.append(l[i])
new_l.append(l[n-1])


for i in range(len(new_l)-1):
    if new_l[i] < new_l[i+1]:
        div = money//new_l[i]
        money += (new_l[i+1]-new_l[i])*div
    
print(money)

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

cash=1000
stock=0
for i in range(n):
  if i==n-1:
    if stock!=0:
      cash+=A[i]*stock
      stock=0
    break
  if A[i]==A[i+1]:pass
  elif A[i]<A[i+1]:
    stock+=cash//A[i]
    cash%=A[i]
  else:
    if stock!=0:
      cash+=A[i]*stock
      stock=0
    
print(cash)

Solution (Python):
import sys
import copy
def S(): return sys.stdin.readline().rstrip()
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def LS(): return list(sys.stdin.readline().rstrip().split())
INF = 1000000000000

n = I()
a = LI()

m = 1000
c = 0
i = 0
while(i < n-1):
    if(c == 0):
        if(a[i] < a[i+1]):
            c = m // a[i]
            m = m % a[i]
    else:
        if(a[i] > a[i+1]):
            m = m + c * a[i]
            c = 0
    i = i+1

if(c != 0):
    m = m + c * a[n-1]

print(m)

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

m = 1000
s = 0

def buy(p):
  global m, s
  s += m // p
  m = m % p

def sell(p):
  global m, s
  m += s * p
  s = 0

for i in range(n-1):
  cur = a[i]
  nxt = a[i+1]
  if cur < nxt:
    if s == 0:
      buy(cur)
  elif cur > nxt:
    if s > 0:
      sell(cur)
if s > 0:
  sell(a[n-1])
print(m)

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

genkin = 1000
kabu = 0

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

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

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

money = 1000
kabu = 0

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

    if arr[i] > arr[i+1]:
        money += kabu*arr[i]
        kabu = 0


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

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

wallet = 1000
stock = 0

for i in range(len(a)-1):
  if a[i+1] > a[i]:
    new_stock = wallet // a[i]
    stock += new_stock
    wallet -= new_stock * a[i]
  elif a[i+1] < a[i]:
    wallet += stock * a[i]
    stock = 0

wallet += stock * a[n-1]

print(wallet)

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

dp = [[0]*(200) for i in range(N)]
kabu0 = 1000

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

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

print(kabu0)

Solution (Python):
N = int(input())
A = list(map(int, input().split()))
sign = 1
mountain, valley = [], []
for i in range(N-1):
  if A[i] < A[i+1]:
    valley.append(0)
    break
  elif A[i] > A[i+1]:
    mountain.append(0)
    break
for i in range(N-1):
  if A[i] > A[i+1]:
    if sign == 1:
      mountain.append(i)
      sign = -1
  elif A[i] < A[i+1]:
    if sign == -1:
      valley.append(i)
      sign = 1
for i in range(N-1, 0, -1):
  if A[i-1] < A[i]:
    mountain.append(N-1)
    break
  elif A[i-1] > A[i]:
    valley.append(N-1)
    break
M = 1000
kb = 0
lm, lv = len(mountain), len(valley)
for i in range(lv):
  flg = True
  cnt = i
  while flg:
    if cnt >= lm:
      flg = False
      break
    elif cnt < lm:
      if mountain[cnt] < valley[i]:
        cnt += 1
      else:
        break
  if flg:
    kb += (M // A[valley[i]])
    M -= (M // A[valley[i]]) * A[valley[i]]
    M += kb * A[mountain[cnt]]
    kb = 0
print(M)

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

Solution (Python):
import sys, os, math, bisect, itertools, collections, heapq, queue, copy, array





sys.setrecursionlimit(10000000)

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: (x * y) // math.gcd(x, y)

MOD = 10 ** 9 + 7
MAX = float('inf')


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N = ii()
    A = il()
    tmp = A[0]
    money = 1000

    for a in A:
        if tmp < a:
            c = money // tmp
            money -= tmp * c
            money += c * a
            tmp = a
        else:
            tmp = min(tmp, a)
    print(money)


if __name__ == '__main__':
    main()

Solution (Python):
def main():
    n = int(input())
    inlis = list(map(int, input().split()))
    
    kabu = 0
    tmp = inlis[0]
    shoji = 1000

    for i in range(0, n-1):
        if inlis[i] > tmp:
            shoji += inlis[i] * kabu
            tmp = inlis[i]
            kabu = 0
            
            if inlis[i+1] > inlis[i]:
                kabu += shoji // inlis[i]
                shoji -= inlis[i] * kabu
                
        elif inlis[i] <= tmp:
            if inlis[i+1] > inlis[i]:
                kabu += shoji // inlis[i]
                shoji -= inlis[i] * kabu
                tmp = inlis[i]
                
    if inlis[n-1] > inlis[n-2]:
        shoji += inlis[n-1] * kabu
        kabu = 0
    print(shoji)





if __name__ == "__main__":
    main()

Solution (Python):





import sys
import heapq

def main():
    n = int(input())
    nums = list(map(int, sys.stdin.readline().split()))

    money = 1000
    stock = 0
    minVal = nums[0]
    maxVal = nums[0]

    if n == 2:
        if nums[0] < nums[1]:
            money = 1000 - (1000 // nums[0]) * nums[0]
            stock = (1000 // nums[0])

            print(money + stock * nums[1])
        else:
            print(1000)
        return

    upFlag = False
    downFlag = False
    
    
    
    
    
    money = 1000
    stock = 0
    for i in range(n - 1):
        
        
        
        if nums[i] < nums[i + 1]:
            if upFlag:
                continue
            else:
                
                tempStock = money // nums[i]
                stock += tempStock
                money -= tempStock * nums[i]
                downFlag = False
                upFlag = True
        
        if nums[i] > nums[i + 1]:
            if downFlag:
                continue
            else:
                
                money += stock * nums[i]
                stock = 0
                downFlag = True
                upFlag = False
        
        
    


    if stock:
        money += stock * nums[-1]

    print(money)
    return

if __name__ == "__main__":
    main()

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

a_pre = A[0]
A_new = [a_pre]
for a in A[1:]:
    if a != a_pre:
        A_new.append(a)
    a_pre = a


minimum = []
maximum = []
N_ = len(A_new)
for i in range(N_):
    max_ = []
    min_ = []
    if i<N_-1:
        s = A_new[i] < A_new[i+1]
        max_.append(not s)
        min_.append(s)
    if i>0:
        s = A_new[i] < A_new[i-1]
        max_.append(not s)
        min_.append(s)
    maximum.append(all(max_))
    minimum.append(all(min_))


stock = False
M = 1000
S = 0
a_pre = None
for max_, min_, a in zip(maximum, minimum, A_new):
    if ~stock and min_:
        S = M // a
        a_pre = a
        stock = True
    if stock and max_:
        M += S * (a-a_pre)
        S = 0

print(M)