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

H, W = map(int, input().split())
maze = []
for _ in range(H):
    maze.append(input())
nodes = []
nodedict = {}
for r in range(H):
    for c in range(W):
        if maze[r][c] == '.':
            node_id = len(nodes)
            nodedict[(r,c)] = node_id
            nodes.append((r,c))
N = len(nodes)
INF = H*W+100
dist = [[INF] * N for _ in range(N)]
for i in range(N):
    dist[i][i] = 0

def connect(r1, c1, r2, c2):
    n1 = nodedict[(r1, c1)]
    n2 = nodedict[(r2, c2)]
    dist[n1][n2] = 1
    dist[n2][n1] = 1

def solve():
    for i in range(N):
        r, c = nodes[i]
        if r > 0 and maze[r-1][c] == '.': connect(r, c, r-1, c)
        if r < H-1 and maze[r+1][c] == '.': connect(r, c, r+1, c)
        if c > 0 and maze[r][c-1] == '.': connect(r, c, r, c-1)
        if c < W-1 and maze[r][c+1] == '.': connect(r, c, r, c+1)

    # Warshall Floyd
    for k in range(N):
        for i in range(N):
            for j in range(N):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

    maxd = 0
    di, dj = None, None
    for i in range(N):
        for j in range(N):
            d = dist[i][j]
            if d < INF and maxd < d:
                maxd = d
                di = nodes[i]
                dj = nodes[j]
    return maxd  #, di, dj


print(solve())


### FIXED CODE ###

H, W = map(int, input().split())
maze = []
for _ in range(H):
    maze.append(input())
nodes = []
nodedict = {}
for r in range(H):
    for c in range(W):
        if maze[r][c] == '.':
            node_id = len(nodes)
            nodedict[(r,c)] = node_id
            nodes.append((r,c))
N = len(nodes)
INF = H*W+100
dist = [[INF] * N for _ in range(N)]
for i in range(N):
    dist[i][i] = 0

def connect(r1, c1, r2, c2):
    n1 = nodedict[(r1, c1)]
    n2 = nodedict[(r2, c2)]
    dist[n1][n2] = 1
    dist[n2][n1] = 1

def solve():
    for i in range(N):
        r, c = nodes[i]
        if r > 0 and maze[r-1][c] == '.':
            connect(r, c, r-1, c)
        if r < H-1 and maze[r+1][c] == '.':
            connect(r, c, r+1, c)
        if c > 0 and maze[r][c-1] == '.':
            connect(r, c, r, c-1)
        if c < W-1 and maze[r][c+1] == '.':
            connect(r, c, r, c+1)

    # Warshall Floyd
    for k in range(N):
        for i in range(N):
            for j in range(N):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

    maxd = 0
    di, dj = None, None
    for i in range(N):
        for j in range(N):
            d = dist[i][j]
            if d < INF and maxd < d:
                maxd = d
                di = nodes[i]
                dj = nodes[j]
    return maxd  #, di, dj


print(solve())
### BUGGY CODE ###

#ないよりも10倍以上早くなる
import sys
input = sys.stdin.readline

K,S=map(int,input().split())
if 2<=K<=2500 and 0<=S<=3*K:
    count=0
    Ks=[]
    wa=[]
    for i in range(K+1):
        Ks.append(i)
    X,Y,Z =Ks,Ks,Ks
    for x in X:
        if x<=S:
            X_=[]
            X_.append(x)
            for y in Y:
                if y<=S:
                    X_Y_=list(X_)
                    X_Y_.append(y)
                    wa_=sum(X_Y_)
                    wa.append(wa_)
    wa= [w for w in wa if w<=S]
    for z in Z:
        for j in wa:
            j+=z
            if j==S:
                count+=1
    print(count)

### FIXED CODE ###

import sys
input = sys.stdin.readline
 
K,S=map(int,input().split())
count=0
for x in range(K+1):
    for y in range(K+1):
        if S-(x+y)>=0 and S-(x+y)<=K: count+=1
print(count)
### BUGGY CODE ###

def main():
    N,K = [int(e) for e in input().split()]
    asiba = [int(e) for e in input().split()]
    dp =[0] *N

    #初期化
    dp[0]=0
    dp[1]=abs(asiba[1]-asiba[0])

    for i in range(2,N):
        dp[i] = min(dp[i-j]+abs(asiba[i]-asiba[i-j]) for j in range(1,min(i+1,K+1)))
    
    print(dp[N-1])
main()

### FIXED CODE ###

def main():
  n, k = [int(e) for e in input().split()]
  h = [int(e) for e in input().split()]
  cost = [0] * n
  for i in range(1, n):
    cost[i] = min(abs(h[i] - h[j]) + cost[j] for j in range(max(0, i - k), i))
  print(cost[n - 1])
main()
### BUGGY CODE ###

N = int(input())
X = input()

def popcount(x):
    tmp = x
    count = 0
    while tmp > 0:
        if tmp & 1 == 1:
            count += 1
        tmp >>= 1
    
    return count

def pow_k(x, n):
    if n == 0:
        return 1
    K = 1
    while n > 1:
        if n % 2 != 0:
            K *= x
        x *= x
        n //= 2

    return K * x

tmp_pop_X = X.count('1')

for i in range(N):
    if X[i] == '0':
        X_next = int(X,2) + pow_k(2,N-1-i)
        X_pop_next = tmp_pop_X + 1
    else:
        X_next = int(X,2) - pow_k(2,N-1-i)
        X_pop_next = tmp_pop_X - 1
        
    if X_pop_next == 0:
        print(0)
        continue
        
    X_next = X_next % X_pop_next
    ans = 1
    
    while X_next != 0:
        X_next = X_next % popcount(X_next)
        ans += 1
        
    print(ans)

### FIXED CODE ###

n = int(input())
s = input()
x = int(s, 2)
pcx = s.count("1")
pc1 = x % (pcx - 1) if pcx > 1 else 0
pc2 = x % (pcx + 1)

def f(j):
    cnt = 0
    while j:
        j %= bin(j).count("1")
        cnt += 1
    return cnt

for i, y in enumerate(s):
    k = n - 1 - i
    if y == "0":
        print(f((pc2 + pow(2, k, pcx + 1)) % (pcx + 1)) + 1)
    elif pcx > 1:
        print(f((pc1 - pow(2, k, pcx - 1)) % (pcx - 1)) + 1)
    else:
        print(0)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import sys 
import itertools
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
H, W, M= map(int,readline().split())
h_cnt = [0]*(H+1)
w_cnt = [0]*(W+1)
data = [[False]*(W+1) for i in range(H+1)]

for i in range(M):
    h,w = map(int,readline().split())
    data[h][w] = True
    h_cnt[h] += 1 
    w_cnt[w] += 1
    
max_h = max(h_cnt)
max_w = max(w_cnt)

max_h_ind = []
max_w_ind = []
max_h_cnt = 0
max_w_cnt = 0

for i in range(H+1):
    if max_h == h_cnt[i]:
        max_h_cnt += 1
        max_h_ind.append(i)

for i in range(W+1):
    if max_w == w_cnt[i]:
        max_w_cnt += 1
        max_w_ind.append(i)
        
t = list(itertools.product(max_h_ind, max_w_ind))

if max_w_cnt * max_h_cnt > M:
    print(max_h+max_w)
else:
    for h,w in t:
        if data[h][w] == False:
            print(max_h+max_w)
            sys.exit()
    print(max_h+max_w-1)

### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys 
import itertools
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
H, W, M = map(int,readline().split())
h_cnt = [0]*(H+1)
w_cnt = [0]*(W+1)
bomb = []
 
for i in range(M):
    h,w = map(int,readline().split())
    bomb.append((h,w))
    h_cnt[h] += 1 
    w_cnt[w] += 1
    
maxh = max(h_cnt)
maxw = max(w_cnt)
maxhCnt = h_cnt.count(maxh)
maxwCnt = w_cnt.count(maxw)

total = maxhCnt*maxwCnt
ans = maxh+maxw
cnt = 0
for h,w in bomb:
    if h_cnt[h] == maxh and w_cnt[w] == maxw:
       cnt += 1

print(ans-1 if cnt == total else ans)
### BUGGY CODE ###

n,m=map(int,input().split())
a=[int(input()) for i in range(m)]
INF=1000000007
dp=[0]*(n+1)
dp[0]=1
if 1 in a:
    dp[1]=0
else:
    dp[1]=1

for i in range(2,n+1):
    if i in a:
        continue
    dp[i]=dp[i-1]+dp[i-2]
    dp[i]%=INF

print(dp[n])



### FIXED CODE ###

n,m=map(int,input().split())
a = set([int(input()) for _ in range(m)])

INF=1000000007
dp=[0]*(n+1)
dp[0]=1
if 1 in a:
    dp[1]=0
else:
    dp[1]=1
for i in range(2,n+1):
    if i in a:
        continue
    dp[i]=dp[i-1]+dp[i-2]
    dp[i]%=INF
print(dp[n])
### BUGGY CODE ###

import sys
import math  # noqa
import bisect  # noqa
import queue  # noqa


def input():
    return sys.stdin.readline().rstrip()


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

    res = K
    step = [-1 for _ in range(N)]
    que = queue.Queue()
    que.put(0)
    step[0] = 0
    while not que.empty():
        nc = que.get()
        nn = A[nc]
        nn -= 1
        res -= 1
        if step[nn] == -1:
            step[nn] = step[nc] + 1
            if res == 0:
                return print(nn + 1)
            que.put(nn)
        else:
            closer = [nn]
            while True:
                if A[nn] - 1 not in closer:
                    nn = A[nn] - 1
                    closer.append(nn)
                else:
                    break
            ans = res % len(closer)
            print(closer[ans] + 1)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
import math  # noqa
import bisect  # noqa
import queue  # noqa


def input():
    return sys.stdin.readline().rstrip()


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

    res = K
    step = [-1 for _ in range(N)]
    que = queue.Queue()
    que.put(0)
    step[0] = 0
    while not que.empty():
        nc = que.get()
        nn = A[nc]
        nn -= 1
        res -= 1
        if step[nn] == -1:
            step[nn] = step[nc] + 1
            if res == 0:
                return print(nn + 1)
            que.put(nn)
        else:
            start = nn
            closer = [nn]
            while True:
                nn = A[nn] - 1
                if nn != start:
                    closer.append(nn)
                else:
                    break
            ans = res % len(closer)
            print(closer[ans] + 1)


if __name__ == '__main__':
    main()
### BUGGY CODE ###

N, *d = map(int, open(0).read().split())
m=max(d)
for i in range(N):
    if(d[i]==m):
        temp=d[i]
        d[i]=0
        y=max(d)
        print(y)
        d[i]=temp     
    else:
        print(m)

### FIXED CODE ###

N, *d = map(int, open(0).read().split())
m=d.index(max(d))
c=[max(d)] *N
d[m]=0
y=max(d)
c[m]=y
for i in range(len(c)):
    print(c[i])
### BUGGY CODE ###

n,m=map(int,input().split())
x=input().split()
for i in range(m):
    a=int(x[i])
    x[i]=a
if n==1:
    print(max(x)-min(x))
elif m==1 or n>=m:
    print(0)
else:
    goukei=0
    l=[0]
    i=0
    x.sort()
    a=0
    b=0
    if m>1:
        while i<m-1:
            a=x[i]
            b=x[i+1]
            goukei+=b-a
            l.append(b-a)
            i+=1
    i=0
    l.sort()
    while i<n-1:
        a=max(l)
        goukei-=a
        l.remove(a)
        i+=1
        if l==[]:
            break
    print(goukei)

### FIXED CODE ###

n,m=map(int,input().split())
x=list(map(int,input().split()))
x.sort()
if n==1:
    print(max(x)-min(x))
elif m==1 or n>=m:
    print(0)
else:
    x.sort()
    goukei=0
    l=[0]
    for i in range(m-1):
        goukei+=x[i+1]-x[i]
        l.append(x[i+1]-x[i])
    i=0
    l.sort()
    for i in range(n-1):
        goukei-=l[-1-i]
    print(goukei)
### BUGGY CODE ###

from collections import Counter
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

N = int(readline())
C = tuple(map(lambda x: int(x)-1, readline().split()))

temp = map(int,read().split())
temp = zip(temp,temp)

adj = [list() for _ in range(N)]
for a,b in temp:
    adj[a-1].append(b-1)
    adj[b-1].append(a-1)


parent = [None]*N
parent[0] = -1

stack = [0]
order = []
while stack:
    p = stack.pop()
    order.append(p)
    for c in adj[p]:
        if parent[c] is None:
            parent[c] = p
            stack.append(c)

dp = [Counter() for _ in range(N)] # color-wise counter
subtreesize = [0]*N
cnt = [N*(N+1)//2]*N

for c in reversed(order):
    p = parent[c]
    if p >= 0:
        dp[c][C[c]] = subtreesize[c]+1
        x = subtreesize[c]-dp[c][C[p]]+1
        cnt[C[p]] -= x*(x+1)//2
        subtreesize[p] += subtreesize[c]+1

        a,b = dp[p],dp[c]
        if len(a) > len(b):
            a += b
            dp[p] = a
        else:
            b += a
            dp[p] = b
        dp[c] = None

dp[0][C[0]] = subtreesize[0]+1
for c in range(N):
    x = subtreesize[0]-dp[0][c]+1
    cnt[c] -= x*(x+1)//2

print(*cnt, sep='\n')


### FIXED CODE ###

from collections import defaultdict
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

N = int(readline())
C = tuple(map(lambda x: int(x)-1, readline().split()))

temp = map(int,read().split())
temp = zip(temp,temp)

adj = [list() for _ in range(N)]
for a,b in temp:
    adj[a-1].append(b-1)
    adj[b-1].append(a-1)


parent = [None]*N
parent[0] = -1

stack = [0]
order = []
while stack:
    p = stack.pop()
    order.append(p)
    for c in adj[p]:
        if parent[c] is None:
            parent[c] = p
            stack.append(c)

def merge(a,b):
    if len(a) > len(b):
        a,b = b,a
    for k,v in a.items():
        b[k] += v
    return b

dp = [defaultdict(int) for _ in range(N)] # color-wise counter
subtreesize = [0]*N
cnt = [N*(N+1)//2]*N

for c in reversed(order):
    p = parent[c]
    if p >= 0:
        dp[c][C[c]] = subtreesize[c]+1
        x = subtreesize[c]-dp[c][C[p]]+1
        cnt[C[p]] -= x*(x+1)//2
        subtreesize[p] += subtreesize[c]+1

        dp[p] = merge(dp[c],dp[p])
        dp[c] = None

dp[0][C[0]] = subtreesize[0]+1
for c in range(N):
    x = subtreesize[0]-dp[0][c]+1
    cnt[c] -= x*(x+1)//2

print(*cnt, sep='\n')
### BUGGY CODE ###

N, M = map(int, input().split())
A = list(map(int, input().split()))
B_C = [list(map(int, input().split())) for j in range(M)]

B_C = sorted(B_C, key=lambda x:x[1], reverse=True)

B = [B_C[j][0] for j in range(M)]
C = [B_C[j][1] for j in range(M)]

D = []
for j in range(M):
    D += [C[j]] * B[j]

A.sort()

for i in range(N):
    if A[i] < D[i]:
        A[i] = D[i]
    else:
        break
    if i == len(D) - 1:
        break

print(sum(A))

### FIXED CODE ###

N, M = map(int, input().split())
A = list(map(int, input().split()))
B_C = [list(map(int, input().split())) for j in range(M)]

B_C = sorted(B_C, key=lambda x:x[1], reverse=True)

B = [B_C[j][0] for j in range(M)]
C = [B_C[j][1] for j in range(M)]

D = []
for j in range(M):
    D += [C[j]] * B[j]
    if len(D) >= N:
        break

A.sort()

for i in range(N):
    if A[i] < D[i]:
        A[i] = D[i]
    else:
        break
    if i == len(D) - 1:
        break

print(sum(A))
### BUGGY CODE ###

N, Q = map(int, input().split())
S = input()
lis = []
for _ in range(Q):
  lis.append(list(map(int, input().split())))
for temp in lis:
  strin = S[temp[0] - 1:temp[1]]
  Tlis = []
  for i in range(len(strin) - 1):
    Tlis.append(strin[i: i + 2])  
  print(Tlis.count("AC"))

### FIXED CODE ###

import bisect
N, Q = map(int, input().split())
S = input()
lis = []
for i in range(len(S) - 1):
  if S[i] == "A" and S[i + 1] == "C":
    lis.append(i + 1)
for _ in range(Q):
  l, r = map(int, input().split())
  ko = bisect.bisect_left(lis, l)
  kk = bisect.bisect_left(lis, r)
  print(kk - ko)
### BUGGY CODE ###

N = int(input())
d = list(map(int, input().split(' ')))
c = 0
mid = (max(d) + min(d))//2
for i in range(mid//2, mid*2):
    a = sum([1 for val in d if val < i])
    b = sum([1 for val in d if val >= i])
    if a == b:
        c += 1
print(c)

### FIXED CODE ###

N = int(input())
d = list(map(int, input().split(' ')))
d.sort()

print( d[N//2] - d[N//2 - 1] )
### BUGGY CODE ###

import sys

def input():
    return sys.stdin.readline().strip()

def trial_division(n):
    prime_factors = list()
    while n % 2 == 0:
        prime_factors.append(2)
        n //= 2
    p = 3
    while p * p <= n:
        if n % p == 0:
            prime_factors.append(p)
            n //= p
        else:
            p += 2
    if n != 1:
        prime_factors.append(n)
    return prime_factors

def keisan(A,B):
    return A**4 + A**3 * B + A**2 * B**2 + A * B ** 3 + B**4

def main():
    X = int(input())
    if X == 1:
        print(1,0)
        exit()
    soinsu = trial_division(X)
    A = 0
    while True:
        A += 1
        B = A - soinsu[0]
        if A**5 - B**5 == X:
            print(A,B)
            exit()


if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys

def input():
    return sys.stdin.readline().strip()

def main():
    X = int(input())
    for A in range(-118,120):
        for B in range(-119,119):
            if A**5 - B**5 == X:
                print(A,B)
                exit()

if __name__ == "__main__":
    main()
### BUGGY CODE ###


# -*- coding: utf-8 -*-
import sys

input = sys.stdin.readline

def slv():
    N, M, L = list(map(int, input().rstrip('\n').split()))
    g = [[sys.maxsize]*(N) for _ in range(N)]
    gg = [[sys.maxsize]*(N) for _ in range(N)]
    
    for i in range(N):
        g[i][i] = 0
    for _ in range(M):
        a, b, c = list(map(int, input().rstrip('\n').split()))
        if c <= L:
            g[a-1][b-1] = c
            g[b-1][a-1] = c
    
    for k in range(N):
        for i in range(N):
            for j in range(N):
                g[i][j] = min(g[i][j], g[i][k] + g[k][j])
    
    for u in range(N):
        for v in range(N):
            if g[u][v] <= L:
                gg[u][v] = 1
    
    for k in range(N):
        for i in range(N):
            for j in range(N):
                gg[i][j] = min(gg[i][j], gg[i][k] + gg[k][j])

    Q = int(input())
    for _ in range(Q):
        s, t = list(map(int, input().rstrip('\n').split()))
        c = gg[s-1][t-1]
        if c != sys.maxsize:
            print(c-1)
        else:
            print(-1)



def main():
    slv()
    # N, M, L = read_int_n()
    # ABC = [read_int_n() for _ in range(M)]
    # Q = read_int()
    # ST = [read_int_n() for _ in range(Q)]
    
    # (slv(N, M, L, ABC, Q, ST))


if __name__ == '__main__':
    main()


### FIXED CODE ###

def slove():
    import sys
    input = sys.stdin.readline
    n, m, l = list(map(int, input().rstrip('\n').split()))
    INF = 10 ** 11
    w = [[INF] * n for _ in range(n)]
    wl = [[INF] * n for _ in range(n)]

    for i in range(n):
        w[i][i] = 0

    for i in range(m):
        a, b, c = list(map(int, input().rstrip('\n').split()))
        if c <= l:
            w[a - 1][b - 1] = c
            w[b - 1][a - 1] = c

    for i in range(n):
        for j in range(n):
            for k in range(n):
                w[j][k] = min(w[j][k], w[j][i] + w[i][k])

    for i in range(n):
        for j in range(n):
            if w[i][j] <= l:
                wl[i][j] = 1
    for i in range(n):
        for j in range(n):
            for k in range(n):
                wl[j][k] = min(wl[j][k], wl[j][i] + wl[i][k])

    q = int(input().rstrip('\n'))
    for i in range(q):
        s, t = list(map(int, input().rstrip('\n').split()))
        if wl[s-1][t-1] == INF:
            print(-1)
        else:
            print(wl[s-1][t-1] - 1)


if __name__ == '__main__':
    slove()
### BUGGY CODE ###

#!/usr/bin/env python3
h,n = map(int,input().split())
a = [0]*n
b = [0]*n
for i in range(n):
    a[i],b[i] = map(int,input().split())
#  dp[i] i 以上の攻撃力を与えるための最小魔力
b,a = zip(*sorted(zip(b,a))) #魔力でソート
dp = [0]*(h+1)
dp[0] = 0
for i in range(1,h+1):
    dp[i] = 10**12
    for j in range(n):#すべての種類の魔法に対してループ
        if i -a[j] >= 0:#魔法が使えるなら
            dp[i] = min(dp[i],dp[i-a[j]]+b[j])
        else: dp[i] = min(dp[i],b[j])
"""print(dp)
print(a,b)"""
print(dp[h])


### FIXED CODE ###

#!/usr/bin/env python3
h,n = map(int,input().split())
a = [0]*n
b = [0]*n
for i in range(n):
    a[i],b[i] = map(int,input().split())
#  dp[i] i 以上の攻撃力を与えるための最小魔力
b,a = zip(*sorted(zip(b,a))) #魔力でソート
dp = [0]*(h+1)
dp[0] = 0
for i in range(1,h+1):
    dp[i] = 10**12
    for j in range(n):#すべての種類の魔法に対してループ
        if i -a[j] >= 0:#魔法が使えるなら
            dp[i] = min(dp[i],dp[i-a[j]]+b[j])
        else: dp[i] = min(dp[i],b[j])
"""print(dp)
print(a,b)"""
print(dp[h])
### BUGGY CODE ###

#from statistics import median
#import collections
#aa = collections.Counter(a) # list to list || .most_common(2)で最大の2個とりだせるお a[0][0]
from fractions import gcd
from itertools import combinations,permutations,accumulate # (string,3) 3回
#from collections import deque
from collections import deque,defaultdict,Counter
import decimal
import re
#import bisect
#
#    d = m - k[i] - k[j]
#    if kk[bisect.bisect_right(kk,d) - 1] == d:
#
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#
# my_round_int = lambda x:np.round((x*2 + 1)//2)
# 四捨五入
import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7
#mod = 9982443453
def readInts():
  return list(map(int,input().split()))
def I():
  return int(input())
n = I()
A = readInts()
lis = []
prv = -1
for i in range(n):
    if prv != A[i]:
        lis.append(A[i])
        prv = A[i]
def dfs(money,kabu,now):
    if now == len(lis):
        global ans
        ans = max(money,ans)
        return
    if kabu != 0:
        if now + 1 == len(lis):
            dfs(money + kabu*lis[now],0,now+1)
        else:
            if lis[now] > lis[now + 1]:
                dfs(money + kabu*lis[now],0,now+1)
    if money//lis[now] >= 1:
        if now + 1 == len(lis):
            dfs(money - lis[now] * (money//lis[now]),money//lis[now],now+1)
        else:
            if lis[now] < lis[now + 1]:
                dfs(money - lis[now] * (money//lis[now]),money//lis[now],now+1)
    dfs(money,kabu,now+1)
ans = 1000
dfs(1000,0,0)
print(ans)


### FIXED CODE ###

#from statistics import median
#import collections
#aa = collections.Counter(a) # list to list || .most_common(2)で最大の2個とりだせるお a[0][0]
from fractions import gcd
from itertools import combinations,permutations,accumulate # (string,3) 3回
#from collections import deque
from collections import deque,defaultdict,Counter
import decimal
import re
#import bisect
#
#    d = m - k[i] - k[j]
#    if kk[bisect.bisect_right(kk,d) - 1] == d:
#
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#
# my_round_int = lambda x:np.round((x*2 + 1)//2)
# 四捨五入
import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7
#mod = 9982443453
def readInts():
  return list(map(int,input().split()))
def I():
  return int(input())
n = I()
A = readInts()
money = 1000
kabu = 0
for i in range(1,n):
    if A[i-1] < A[i]:
        kabu = money // A[i-1]
        money -= kabu * A[i-1]
        money += kabu * A[i]
        kabu = 0
    #print(money,kabu)
print(money)
### BUGGY CODE ###

def f(a,b,x):
	return int(a*x/b) - a*int(x/b)

a,b,n = map(int,input().split())
print(max([f(a,b,x) for x in range(1,n+1)]))



### FIXED CODE ###


def f(a,b,x):
	return int(a*x/b) - a*int(x/b)

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

if n < b:
	print(f(a,b,n))
else:
	print(f(a,b,b-1))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(500000)

def dfs(v,d,p):
    memo[v] = d
    for i in graph[v]:
        if memo[i[0]] != -1:continue
        dfs(i[0],d+i[1],v)
    sub_tree[v].append(v)
    for j in graph[v]:
        if j[0] == p:continue
        sub_tree[v] += sub_tree[j[0]]
    if p == k-1:arr.append(sub_tree[v])
n = int(input())
graph = [[] for _ in range(n)]
memo = [-1]*n

for i in range(n-1):
    x,y,z = map(int,input().split())
    graph[x-1].append([y-1,z])
    graph[y-1].append([x-1,z])
q,k = map(int,input().split())
sub_tree = [[] for _ in range(n)]
arr = []
ary = [list(map(int,input().split())) for _ in range(q)]
dfs(k-1,0,0)
arr.pop()
print(*[memo[x-1]+memo[y-1] for x,y in ary],sep="\n")

### FIXED CODE ###

import sys
sys.setrecursionlimit(500000)

def dfs(v,d):
    memo[v] = d
    for i in graph[v]:
        if memo[i[0]] != -1:continue
        dfs(i[0],d+i[1])
        
n = int(input())
graph = [[] for _ in range(n)]
memo = [-1]*n
for i in range(n-1):
    x,y,z = map(int,input().split())
    graph[x-1].append([y-1,z])
    graph[y-1].append([x-1,z])
q,k = map(int,input().split())
ary = [list(map(int,input().split())) for _ in range(q)]
dfs(k-1,0)
print(*[memo[x-1]+memo[y-1] for x,y in ary],sep="\n")
### BUGGY CODE ###

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

for i in range(n-1):
    ans += (sum(a[0:i+1])%1000000007)*(a[i+1]%1000000007)

print(ans%1000000007)


### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
ans = 0
a_sum = [a[0]]

for i in range(n-1):
    a_sum.append((a_sum[i]+a[i+1])%1000000007)

    ans += a_sum[i]*(a[i+1]%1000000007)

print(ans%1000000007)