Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

import sys
readline = sys.stdin.buffer.readline
from collections import deque
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7


def main():
    H, W, K = map(int, readline().split())
    # いつものパターンと問題文のi,jが逆なので、
    # 問題文のxを変数yに、問題文のyを変数xに代入している
    sy, sx, gy, gx = map(int, readline().split())
    lake = [['@' for _ in range(W+2)]]

    for _ in range(H):
        c = ['@'] + list(readline().decode('utf-8').strip()) + ['@']
        lake.append(c)
    lake.append(['@' for _ in range(W+2)])

    dist = [[INF] * (W+2) for _ in range(H+2)]
    dx = (1, 0, -1, 0)
    dy = (0, 1, 0, -1)
    Q = deque()
    Q.append((sy, sx))
    dist[sy][sx] = 0
    while Q:
        y,x = Q.popleft()
        if y == gy and x == gx:
            break
        for i in range(4):
            for k in range(1,K+1):
                n_y = y + dy[i] * k
                n_x = x + dx[i] * k

                if lake[n_y][n_x] == '.':
                    if dist[n_y][n_x] > dist[y][x]+1:
                        dist[n_y][n_x] = dist[y][x] + 1
                        Q.append((n_y,n_x))
                    else:
                        continue

                else:
                    break

    if dist[gy][gx] == INF:
        print('-1')
    else:
        print(dist[gy][gx])


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
from collections import deque
 
H, W, K = map(int,readline().split())
x1, y1, x2, y2 = map(int,readline().split())
x1 -= 1; y1 -= 1; x2 -= 1; y2 -= 1
C = read().split()

dist = [[-1]*W for i in range(H)]
dist[x1][y1] = 0
d = deque([[x1, y1]])
dxy= [[1, 0], [0, 1], [-1, 0], [0, -1]]
while d:
  x, y = d.popleft()
  if (x, y) == (x2, y2):
    print(dist[x][y])
    quit()
  for dx, dy in dxy:
    xx = x; yy = y
    for i in range(K):
      xx += dx; yy += dy
      if 0<=xx<H and 0<=yy<W and C[xx][yy]!='@':
        if 0 <= dist[xx][yy] <= dist[x][y]:
          break
        if dist[xx][yy] == -1:
           d.append([xx, yy])
        dist[xx][yy] = dist[x][y] + 1
      else:
        break

print(-1)
### BUGGY CODE ###

#c welcome to atcoder
import sys
n,m=map(int,input().split())
ps=[]
num={}
correct=[]
#辞書
ac=0
pena=0
if m==0:
    print('0 0')
    sys.exit()
for i in range(m):
    result=input().split()
    ps.append(result)
    if result[1]=="AC":
        correct.append(result[0])

for x in ps:
    if not x[0] in correct:
        continue
    if x[0] not in num:
        num[x[0]]=0
    if x[1]=="WA" and num[x[0]]==0:
        pena+=1
    if x[1]=="AC" and num[x[0]]==0:
        ac+=1
        num[x[0]]=1

print(ac,pena)

### FIXED CODE ###

#c welcome to atcoder
import sys
n,m=map(int,input().split())
ps=[]
num={}
#辞書
ac=0
pena=0
if m==0:
    print('0 0')
    sys.exit()
for i in range(m):
    result=input().split()
    ps.append(result)
    if result[1]=="AC":
        num[result[0]]=0

for x in ps:
    if not x[0] in num:
        continue
    if x[1]=="WA" and num[x[0]]==0:
        pena+=1
    if x[1]=="AC" and num[x[0]]==0:
        ac+=1
        num[x[0]]=1

print(ac,pena)
### BUGGY CODE ###

import itertools as itr

N, K = tuple(int(i) for i in input().split())

n = int(N/K)
c1 = list(itr.product(range(n), repeat=3))
c1 = len(c1)

k_2 = K/2

if N < k_2:
    print(0)
elif K%2 != 0:
    print(c1)
else:

    if N < n*K + k_2:
        c2 = list(itr.product(range(n), repeat=3))
    else:
        c2 = list(itr.product(range(n+1), repeat=3))

    c2 = len(c2)
    print(c1 + c2)

### FIXED CODE ###

import math
def cc(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))


N, K = tuple(int(i) for i in input().split())

n = int(N/K)
c1 = n**3

k_2 = K/2

if N < k_2:
    print(0)
elif K%2 != 0:
    print(c1)
else:

    if N < n*K + k_2:
        c2 = n**3
    else:
        c2 = (n+1)**3
    print(c1 + c2)
### BUGGY CODE ###

def f7(seq):
    seen = set()
    seen_add = seen.add
    return [ x for x in seq if x not in seen and not seen_add(x)]


while(1):
    [N,M]=[int(x) for x in raw_input().split()]
    if N==0:
        break
    a=[0]
    for i in range(N):
        a.append(int(raw_input()))
    #b=sorted([x+y for x in a for y in a])
    #c=[]
    #for i in range(1,len(b)):
    #    if b[i]>M:
    #        break
    #    elif b[i-1]!=b[i]:
    #        c.append(b[i-1])
    b=[x+y for x in a for y in a]
    c=f7(b)
    c.sort()
    largest=c[-1]
    id=0
    for i in range(1,len(c)+1):
        if id==len(c):
            break
        while(id<len(c) and c[-i]+c[id]<=M):
            largest=max(largest,c[-i]+c[id])
            if largest==M:
                break
            id+=1
    print largest

### FIXED CODE ###

import bisect

while(1):
    [N,M]=[int(x) for x in raw_input().split()]
    if N==0:
        break
    a=[0 for x in range(N+1)]
    for i in range(N):
        a[i+1]=int(raw_input())
    #b=sorted([x+y for x in a for y in a])
    #c=[]
    #for i in range(1,len(b)):
    #    if b[i]>M:
    #        break
    #    elif b[i-1]!=b[i]:
    #        c.append(b[i-1])
    b=[a[x]+a[y] for x in range(N+1) for y in range(x,N+1)]
    #c=f7(b)
    c=sorted(b)
    #print c
    largest=0
    id=0
    st=len(c)-bisect.bisect(c,M)+1
    #print st
    for i in range(st,len(c)+1):
        if id==len(c):
            break
        while(id<len(c) and c[-i]+c[id]<=M):
            #print c[-i],c[id],c[-i]+c[id]
            largest=max(largest,c[-i]+c[id])
            id+=1
    print largest
### BUGGY CODE ###

def combination(n,r,mod=10**9+7):
    n1 = n+1
    r = min(r,n-r)
    numer = denom = 1
    for i in range(1,r+1):
        numer = numer * (n1-i) % mod
        denom = denom * i % mod
    return numer * pow(denom,mod-2,mod) % mod

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

num = {}
for i in A:
    if i not in num:
        num[i] = 1
    else:
        num[i] += 1


values = list(num.values())
keys = list(num.keys())
S = 0
for i in range(len(keys)):
    if values[i] >= 2:
        S += combination(values[i],2)

for i in range(N):
    if num[A[i]] >= 3:
        print(S-combination(num[A[i]],2)+combination(num[A[i]]-1,2))
    elif num[A[i]] == 2:
        print(S-1)
    else:
        print(S)

### FIXED CODE ###


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

num = {}
for i in A:##O(N)
    if i not in num:
        num[i] = 1
    else:
        num[i] += 1


values = list(num.values())
keys = list(num.keys())
S = 0
for i in range(len(keys)):##O(N*2)
    if values[i] >= 2:
        S += values[i]*(values[i]-1)//2

for i in range(N):
    if num[A[i]] >= 3:
        print(S-num[A[i]]*(num[A[i]]-1)//2+(num[A[i]]-1)*(num[A[i]]-2)//2)
    elif num[A[i]] == 2:
        print(S-1)
    else:
        print(S)
### BUGGY CODE ###

# AtCoder Beginner Contest 077 C - Snuke Festival　

import sys

N = int(input())
A = list(map(int, sys.stdin.readline().strip().split()))
B = list(map(int, sys.stdin.readline().strip().split()))
C = list(map(int, sys.stdin.readline().strip().split()))

A = sorted(A)
B = sorted(B)
C = sorted(C)


def search(i, S):  # i : search する数値  S: search対象の数列
    if S[0] > i:
        return len(S)
    if S[-1] <= i:
        return 0

    left = 0
    right = len(S) - 1

    while right - left != 1:
        # print(f'right:{right}, left:{left}')
        mid = int((left + right) / 2)
        if S[mid] <= i:
            left = mid
        else:
            right = mid

    return len(S) - (left + 1)


ans = 0
for a in A:
    b_num = search(a, B)
    if b_num == 0:
        continue
    for b in B[-b_num:]:
        # print(f'a: {a}, b: {b}')
        c_num = search(b, C)
        # print(f'c_num: {c_num}')
        # print(a, b, C[-c_num])
        ans += c_num

print(ans)


### FIXED CODE ###

# AtCoder Beginner Contest 077 C - Snuke Festival　

import sys

N = int(input())
A = list(map(int, sys.stdin.readline().strip().split()))
B = list(map(int, sys.stdin.readline().strip().split()))
C = list(map(int, sys.stdin.readline().strip().split()))

A = sorted(A)
B = sorted(B)
C = sorted(C)


def search(i, S):  # i : search する数値  S: search対象の数列　　大きいものの個数を返す
    if S[0] > i:
        return len(S)
    if S[-1] <= i:
        return 0

    left = 0
    right = len(S) - 1

    while right - left != 1:
        # print(f'right:{right}, left:{left}')
        mid = int((left + right) / 2)
        if S[mid] <= i:
            left = mid
        else:
            right = mid

    return len(S) - (left + 1)


def search1(i, S):  # i : search する数値  S: search対象の数列  小さいものの個数を返す
    if S[0] >= i:
        return 0
    if S[-1] < i:
        return len(S)

    left = 0  # 満たす
    right = len(S) - 1  # 満たさない

    while right - left != 1:
        mid = int((left + right) / 2)
        if S[mid] < i:
            left = mid
        else:
            right = mid

    return left + 1


ans = 0
for b in B:
    ans_a = search1(b, A)
    ans_c = search(b, C)

    ans += ans_a * ans_c

print(ans)
### BUGGY CODE ###

N=int(input())
S=[]
for i in range(N):
    S.append(input())

Ssort=[sorted(s) for s in S]

counter=0
for i in range(N):
    for j in range(i+1,N):
        if(Ssort[i]==Ssort[j]):
            counter=counter+1

print(counter)



### FIXED CODE ###

N=int(input())
S=[]
for i in range(N):
    S.append(input())

Ssort=[sorted(s) for s in S]
sort2=sorted(Ssort)

total=0
counter=0
ref=sort2[0]
for i in range(1,N):
    if(sort2[i]==ref):
        counter=counter+1
        if(i==N-1):
            total=total+sum(list(range(counter+1)))
    else:
        total=total+sum(list(range(counter+1)))
        counter=0
        ref=sort2[i]

print(total)
### BUGGY CODE ###

N=int(input())
josi = list(map(int,input().split()))
n=1
m=0
count=0
while n<=N:
  m = n-1 
  while m<N-1:
    if josi[m]==n:
      count = count+1
    m=m+1
  print(count)
  n=n+1
  m=0
  count=0

      

### FIXED CODE ###

N=int(input())
josi = list(map(int,input().split()))
count=[0]*N
n=0
while n<N-1:
  count[josi[n]-1] =count[josi[n]-1]+1
  n=n+1
n=0
while n<N:
  print(count[n])
  n=n+1
### BUGGY CODE ###

[N, M] = list(map(int, input().split(' ')))
card_list = list(map(int, input().split(' ')))

card_list.sort()

C_list = []
for i in range(M):
  [B, C] = list(map(int, input().split(' ')))
  for k in range(B):
    C_list.append(C)
  
C_list.sort()

ans = 0
count = 0
for i in range(N):
  if card_list[-1] > C_list[-1]:
    ans += card_list.pop()
    count += 1
  else:
    ans += C_list.pop()
    count += 1
    
  if C_list == []:
    for k in range(N - count):
      ans += card_list.pop()
    break
      
print(ans)
  
                

### FIXED CODE ###

[N, M] = list(map(int, input().split(' ')))
card_list = list(map(int, input().split(' ')))

card_list.sort()
compare_list = []

for i in range(M):
  (B, C) = list(map(int, input().split(' ')))
  compare_list.append((C,B))
    
compare_list.sort()

ans = 0
for i in range(N):
  if compare_list == []:
    ans += sum(card_list[i:])
    break
  if card_list[-1] > compare_list[-1][0]:
    ans += card_list.pop()
  elif compare_list[-1][1] > 0:
    ans += compare_list[-1][0]
    tmp = compare_list.pop()
    a = tmp[0]
    b = tmp[1]
    if b != 1:
      compare_list.append((a,b-1)) 
      
print(ans)
### BUGGY CODE ###

#!/usr/bin/env python3
# coding: utf-8
# import pprint
# import numpy as np
# import code
import functools

def debug(arg):
    if __debug__:
        pass
    else:
        import sys
        debug = lambda *x: None
        print(arg, file=sys.stderr)

n, x, y = (int(x) for x in input().split())
d = dict.fromkeys(range(1, n), 0)
debug(d)
for i in range(1, n):
    for j in range(i + 1, n + 1):
        debug([i, j, x, y])
        dd1=abs(x - i) + 1 + abs(y - j)
        dd2= j - i
        d[min(dd1, dd2)] += 1
        debug(d)

for n in d.values():
    print(n)




### FIXED CODE ###

#!/usr/bin/env python3
# coding: utf-8
# import pprint
# import numpy as np
# import code
import functools

if __debug__:
    def debug(arg):
        pass
else:
    import sys
    def debug(arg):
        debug = lambda *x: None
        print(arg, file=sys.stderr)

n, x, y = (int(x) for x in input().split())
d = dict.fromkeys(range(1, n), 0)
debug(d)
for i in range(1, n):
    for j in range(i + 1, n + 1):
        debug([i, j, x, y])
        dd1=abs(x - i) + 1 + abs(y - j)
        dd2= j - i
        if dd1 < dd2:
            d[dd1] += 1
        else:
            d[dd2] += 1
        debug(d)

for n in d.values():
    print(n)
### BUGGY CODE ###

import sys

sys.setrecursionlimit(1000000)

div_cache = {}
def primes(N):
    if N in div_cache:
        return div_cache[N]
    ret = set()
    for i in range(1, min(int(pow(N, 0.5) + 1), N)):
        if N % i == 0:
            ret.add(i)
            if i != 1:
                ret.add(N // i)
    div_cache[N] = ret
    return ret



def slowsolve(N, K):
    import itertools
    import math
    data = {}
    s = 0
    KK = [i for i in range(1, K + 1)]
    for p in itertools.product(KK, repeat=N):
        cdi = p[0]
        for c in p:
            cdi = math.gcd(cdi, c)
        s += cdi
        data.setdefault(cdi, 0)
        data[cdi] += 1
    print(data)
    return s


def solve(N, K):
    M = pow(10, 9) + 7
    ans = 0
    for i in range(1, K + 1):
        P = pow(K // i, N, M)
        ans += i * P

        def past(prim, sign):
            nonlocal ans
            ans += sum(prim) * P * sign
            ans %= M
            for p in prim:
                if p != 1:
                    past(primes(p), sign * -1)

        past(primes(i), -1)
        ans %= M
    return ans


if __name__ == "__main__":
    N, K = tuple(map(int, input().split(" ")))
    print(solve(N, K))


### FIXED CODE ###

import sys

sys.setrecursionlimit(1000000)

def slowsolve(N, K):
    import itertools
    import math
    data = {}
    s = 0
    KK = [i for i in range(1, K + 1)]
    for p in itertools.product(KK, repeat=N):
        cdi = p[0]
        for c in p:
            cdi = math.gcd(cdi, c)
        s += cdi
        data.setdefault(cdi, 0)
        data[cdi] += 1
    print(data)
    return s


cache = {}
def solve(N, K):
    M = pow(10, 9) + 7
    ans = 0
    for i in range(K, 0, -1):
        P = pow(K // i, N, M)
        j = i + i
        while j <= K:
            P -= cache[j]
            j += i
        while P < 0:
            P += M

        cache[i] = P
        ans += i * P
        ans %= M
    return ans

if __name__ == "__main__":
    N, K = tuple(map(int, input().split(" ")))
    print(solve(N, K))
### BUGGY CODE ###

n, m, q = map(int, input().split())
lr = [tuple(map(int, input().split())) for _ in range(m)]
pq = [tuple(map(int, input().split())) for _ in range(q)]

for i in range(q):
    p, q = pq[i]
    c = 0
    for j in range(m):
        l, r = lr[j]
        if p <= l and r <= q:
            c += 1
    print(c)


### FIXED CODE ###

N, M, Q = map(int, input().split())

x = [[0 for j in range(N + 1)] for i in range(N + 1)]

for _ in range(M):
    L, R = map(int, input().split())
    x[N - L][R] += 1

for i in range(1, N + 1):
    for j in range(1, N + 1):
        x[i][j] += x[i][j - 1]

for j in range(1, N + 1):
    for i in range(1, N + 1):
        x[i][j] += x[i - 1][j]

for _ in range(Q):
    p, q = map(int, input().split())
    print(x[N - p][q])
### BUGGY CODE ###

while True:
  n = input()
  if n == "0000":
    break
  if n.count(n[0]) == 4:
    print("NA")
    continue
  cnt = 0
  while n != "6174":
    cnt += 1
    l = int("".join(sorted(list(str(n)), reverse=True)))
    s = int("".join(sorted(list(str(n)))))
    n = str(l - s)
  print(cnt)





### FIXED CODE ###

while True:
  n = input()
  if n == "0000":
    break
  if n.count(n[0]) == 4:
    print("NA")
    continue
  cnt = 0
  while n != "6174":
    cnt += 1
    l = "".join(sorted(list(n), reverse=True))
    s = "".join(sorted(list(n)))
    n = str(int(l) - int(s)).zfill(4)
  print(cnt)
### BUGGY CODE ###

from collections import deque
H,W = map(int, input().split())
s = [input() for _ in range(H)]

ans = 0
kaburi = 0
for i in range(H):
    for j in range(W):
        if s[i][j]==".": continue
        stk = deque([(i,j)]) # stktack
        visited = set([(i,j)])
        popl = stk.popleft
        append = stk.append
        add = visited.add
        while stk: # なくなるまで
            y,x = popl()

            for dy,dx in ([1,0],[0,1],[-1,0],[0,-1]): 
                if 0 <= y+dy < H and 0 <= x+dx < W:
                    from_ = s[y][x]
                    to_   = s[y+dy][x+dx]
                    if ((from_=="." and to_ == "#")
                     or (from_=="#" and to_ == ".") ):
                        if (y+dy,x+dx) in visited: continue
                        append([y+dy,x+dx])
                        add((y+dy,x+dx))
                        # print(i,j, y+dy,x+dx, ans)
                        if to_=="#": kaburi += 1
                        ans += 1
print(ans-kaburi)

### FIXED CODE ###

class UnionFind:
    """
    - sizeを指定
    - 要素をグループにまとめる(unite) 
    - 要素同士が同じグループか判定する(isSame)
    - 分離はできない
    - par: 親の番号(はじめ par[i]==i つまりすべての頂点が根)
    - 始め各要素は別々のグループ"""
    def __init__(self, size: int):
        self.par = [-1]*size
        for i in range(size):
            self.par[i] = i 
    
    def root(self, x: int) -> int:
        """根を求める"""
        if self.par[x] == x: # if root
            return x
        else:
            self.par[x] = self.root(self.par[x]) # 経路圧縮
            return self.par[x]
    
    def isSame(self, x:int, y:int)->bool:
        """x と y が同じ集合に属するか否か"""
        return self.root(x)==self.root(y)
    
    def unite(self, x:int, y:int):
        """x と y の属する集合を併合"""
        x = self.root(x)
        y = self.root(y)
        if x == y: return
        self.par[x] = y


H,W = map(int, input().split())
s = [input() for _ in range(H)]
uf = UnionFind(H*W) 

def pos2int(h,w):
    # 座標->[0 - H*W]
    return h*W + w

for h in range(H):
    for w in range(W):        
        for dh, dw in zip((0, 1), (1, 0)):
            if not(0<=h+dh<H and 0<=w+dw<W):
                continue
            if s[h][w] != s[h+dh][w+dw]: # 同じグループにする
                uf.unite(pos2int(h, w), pos2int(h+dh, w+dw))
                
white = [0] * H*W
black = [0] * H*W
 
for h in range(H):
    for w in range(W):
        n = pos2int(h, w)
        r = uf.root(n)
        # print(n, r)
        if s[h][w] == ".":
            white[r] += 1
        else:
            black[r] += 1
# print(white)
# print(black)
ans = 0
for h in range(H):
    for w in range(W):
        n = pos2int(h, w)
        ans += white[n] * black[n]
print(ans)
### BUGGY CODE ###

n=int(input())
num = 1
div=int(1e9)+7
for i in range(1,n+1):
  num *= i
print(num%div)

### FIXED CODE ###

n=int(input())
num = 1
div=int(1e9)+7
for i in range(1,n+1):
  num = num*i%div
print(num)
### BUGGY CODE ###

n, k, q = list(map(int, input().split()))
a = []
for i in range(q):
  a.append(int(input()))

cur_k = [k] * n

for i in range(q):
  for j in range(n):
    if (a[i] - 1) != j:
      cur_k[j] -= 1
#  print(a[i], cur_k)
    

for i in cur_k:
  if (i > 0):
    print("Yes")
  else:
    print("No")

### FIXED CODE ###

n, k, q = list(map(int, input().split()))
a = [0] * q
for i in range(q):
  a[i] = int(input())

cur_k = [k] * n

for i in range(q):
  cur_k[a[i] - 1] += 1

for i in cur_k:
  if (i > q):
    print("Yes")
  else:
    print("No")
### BUGGY CODE ###

import sys
input = sys.stdin.readline

N=int(input().rstrip('\n'))
A=[int(x) for x in input().rstrip('\n').split()]
res = 0
t=1
for _ in range(60):
  n = sum(x%2 for x in A)
  A = [x//2 for x in A]
  res += n*(N-n)*t
  t = t*2
  res = res%(7+10**9)
  if all(x==0 for x in A):
    break
print(res)

### FIXED CODE ###

import sys
input = sys.stdin.readline

N=int(input().rstrip('\n'))
A=[int(x) for x in input().rstrip('\n').split()]
res = 0
t=1
for _ in range(60):
  n = sum(x%2 for x in A)
  A = [x//2 for x in A]
  res += n*(N-n)*t
  t = t*2
  res = res%(7+10**9)
  if all(x==0 for x in A):
    break
print(res)
### BUGGY CODE ###

def sekiwa(x):
    n = len(x)
    result = 0
    MOD = 1000000007
    for i in range(n-1):
        for j in range(i+1, n):
            N = nums[i]*nums[j] % MOD
            result += N
            result = result % MOD
    return result

n = int(input())
nums = list(map(int, input().split()))
print(sekiwa(nums))

### FIXED CODE ###

MOD = 1000000007
n = int(input())
nums = list(map(int, input().split()))
x = sum(nums)
y = sum([(nums[i]**2) for i in range(n)])
print(((x**2 - y)//2)% MOD)
### BUGGY CODE ###

import io
import os

from collections import Counter, defaultdict, deque


from functools import lru_cache
import sys

sys.setrecursionlimit(10 ** 5)


def solve(N, A):
    def maxProfitAtEnd(i, money, stocks):
        if i == N - 1:
            # Sell all remaining
            return money + stocks * A[i]

        # no op
        best = maxProfitAtEnd(i + 1, money, stocks)
        # sell
        for numStock in range(1, stocks + 1):
            best = max(
                best, maxProfitAtEnd(i + 1, money + numStock * A[i], stocks - numStock)
            )
        # buy
        for numStock in range(1, (money // A[i]) + 1):
            best = max(
                best, maxProfitAtEnd(i + 1, money - numStock * A[i], stocks + numStock)
            )
        return best

    return maxProfitAtEnd(0, 1000, 0)


if __name__ == "__main__":
    input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

    (N,) = [int(x) for x in input().split()]
    A = [int(x) for x in input().split()]
    ans = solve(N, A)
    print(ans)


### FIXED CODE ###

import io
import os

from collections import Counter, defaultdict, deque


from functools import lru_cache
import sys

sys.setrecursionlimit(10 ** 5)


def solve(N, A):
    @lru_cache(maxsize=None)
    def maxProfitAtEnd(i, money, stocks):
        if i == N - 1:
            # Sell all remaining
            return money + stocks * A[i]

        # no op
        best = maxProfitAtEnd(i + 1, money, stocks)
        # sell
        best = max(best, maxProfitAtEnd(i + 1, money + stocks * A[i], 0))
        # buy
        numStock = money // A[i]
        best = max(
            best, maxProfitAtEnd(i + 1, money - numStock * A[i], stocks + numStock)
        )

        return best

    return maxProfitAtEnd(0, 1000, 0)


def solve(N, A):
    money = 1000
    stock = 0
    for i in range(N - 1):
        if A[i] < A[i + 1]:
            # Buy on i
            numStock = money // A[i]
            money -= numStock * A[i]
            stock += numStock
            # Sell on i + 1
            money += stock * A[i + 1]
            stock = 0
    assert stock == 0
    return money


if __name__ == "__main__":
    input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

    (N,) = [int(x) for x in input().split()]
    A = [int(x) for x in input().split()]
    ans = solve(N, A)
    print(ans)