CodeEff/ECCO huggingface dataset:
# Original solution
class UnionFind:
    def __init__(self, size):
        self.parent = [-1 for i in range(size)]#非負なら親ノード，負ならグループの要素数

    def root(self, x):
        if self.parent[x] < 0:
            return x
        else:
            self.parent[x] = self.root(self.parent[x]) #xをxの根に直接つなぐ
            return self.parent[x]

    def union(self, x, y):
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return False

        if self.parent[x] < self.parent[y]: #xの要素数がyの要素数より「小さい」とき
            x,y=y,x
        self.parent[x] += self.parent[y] #xの要素数を更新
        self.parent[y] = x #yをxにつなぐ
        return True

    def same(self, x, y):
        return self.root(x) == self.root(y)



n,m = list(map(int,input().split()))
p = list([int(x)-1 for x in input().split()])

uf = UnionFind(n)
for i in range(m):
    x,y=list(map(int,input().split()))
    uf.union(x-1,y-1)

ans = 0
for i in range(n):
    if uf.same(i,p[i]):
        ans += 1

print(ans)

# Optimized solution
class UnionFind:
    def __init__(self, size):
        self.parent = [-1 for i in range(size)]#非負なら親ノード，負ならグループの要素数

    def root(self, x): #root(i): $i$の根ノードを返す．
        if self.parent[x] < 0:
            return x
        else:
            self.parent[x] = self.root(self.parent[x]) #xをxの根に直接つなぐ
            return self.parent[x]

    def union(self, x, y): #union(i,j): $i$のいるグループと$j$のいるグループをまとめる
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return False
        if self.parent[x] > self.parent[y]: #xの要素数がyの要素数より「小さい」とき
            x,y=y,x
        self.parent[x] += self.parent[y] #xの要素数を更新
        self.parent[y] = x #yをxにつなぐ
        return True

    def same(self, x, y): #same(i,j): $i$と$j$ が同じグループにあるならTrue，違うならFalse
        return self.root(x) == self.root(y)
        
    def size(self,x): #size(i): $i$のいるグループの要素数を返す
        return -self.parent[self.root(x)]
#>>>>>>>>>>>>>>EhdCutHere>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>

n,m = list(map(int,input().split()))
p = list([int(x)-1 for x in input().split()])

uf = UnionFind(n)
for i in range(m):
    x,y=list(map(int,input().split()))
    uf.union(x-1,y-1)

ans = 0
for i in range(n):
    if uf.same(i,p[i]):
        ans += 1

print(ans)
#print([uf.root(i) for i in range(n)])
#print([uf.parent[i] for i in range(n)])
#print([uf.size(i) for i in range(n)])
# Original solution
from collections import deque

N,M = list(map(int,input().split()))
P = list(map(int,input().split()))
L = [list(map(int,input().split())) for i in range(M)]

G = [[] for i in range(N)]

for i in range(len(L)) :
    u,v = L[i]
    u -= 1
    v -= 1
    
    G[u].append(v)
    G[v].append(u)

explored = [0 for i in range(N)]

ans = 0

for i in range(N) :
    
    if explored[i] :
        continue
    
    explored[i] = 1
    q = deque([i])
    
    A = []
    B = []
    while q :
        now = q.popleft()
        
        A.append(now)
        B.append(P[now]-1)
        
        for to in G[now] :
            if explored[to] :
                continue
            
            q.append(to)
            explored[to] = 1
    
    C = set(A) & set(B)
    ans += len(C)
    

print(ans)
  

# Optimized solution
class UnionFind:
    def __init__(self, num):
        self.rank = [0] * num
        self.par = [i for i in range(num)]
        self.n = num

    def find_root(self, node):
        if self.par[node] == node:
            return node
        else:
            self.par[node] = self.find_root(self.par[node])
            return self.par[node]

    def same_root(self, x, y):
        return self.find_root(x) == self.find_root(y)

    def union(self, x, y):
        x = self.find_root(x)
        y = self.find_root(y)
        if x == y:
            return
        if self.rank[x] > self.rank[y]:
            self.par[y] = x
        else:
            self.par[x] = y
            if self.rank[x] == self.rank[y]:
                self.rank[y] += 1


def main():
    N, M = list(map(int,input().split()))
    L = list(map(int,input().split()))
    UF = UnionFind(N)
    
    for i in range(M) :
        A, B = list(map(int,input().split()))
        A -= 1
        B -= 1
        UF.union(A, B)
    
    ans = 0
    
    for i, v in enumerate(L) :
        ans += (UF.same_root(i, v-1))
    
    print(ans)
    
        

import sys
input = sys.stdin.readline

if __name__ == "__main__":
    main()
# Original solution
import sys
sys.setrecursionlimit(2000000)
input = sys.stdin.readline
class UnionFind():
    def __init__(self,n):
        self.n=n
        self.parents = [i for i in range(n+1)]
        self.size = [1]*(n+1)

    def find(self,x):
        if self.parents[x]==x:
            return x
        else:
            self.parents[x]=self.find(self.parents[x])
            return self.parents[x]

    def union(self,x,y):
        xRoot = self.find(x)
        yRoot = self.find(y)
        if xRoot == yRoot:
            return
        if self.size[xRoot]>self.size[yRoot]:
            self.parents[yRoot] = xRoot
        else:
            self.parents[xRoot] = yRoot
            if self.size[xRoot] == self.size[yRoot]:
                self.size[yRoot]+=1

N,M = list(map(int,input().split()))
P = list(map(int,input().split()))
dic = {}
dic2 = {}
for i in range(1,N+1):
    dic[P[i-1]]=i
    dic2[i]=P[i-1]

tree = UnionFind(N)
for _ in range(M):
    x,y = list(map(int,input().split()))
    tree.union(x,y)

indexGroup = {}
for i in range(1,N+1):
    root = tree.find(i)
    if root not in indexGroup:
        indexGroup[root]=set()
    indexGroup[root].add(i)

for p,i in list(dic.items()):
    root = tree.find(i)
    if p in indexGroup[root]:
        n = dic2[p]
        dic[p] = p
        dic2[p] = p
        dic[n] = i
        dic2[i] = n

count = 0
for p,i in list(dic.items()):
    if p==i:
        count += 1
print(count)



# Optimized solution
import sys
sys.setrecursionlimit(2000000)
input = sys.stdin.readline
class UnionFind():
    def __init__(self,n):
        self.n=n
        self.parents = [i for i in range(n+1)]
        self.size = [1]*(n+1)

    def find(self,x):
        if self.parents[x]==x:
            return x
        else:
            self.parents[x]=self.find(self.parents[x])
            return self.parents[x]

    def union(self,x,y):
        xRoot = self.find(x)
        yRoot = self.find(y)
        if xRoot == yRoot:
            return
        if self.size[xRoot]>self.size[yRoot]:
            self.parents[yRoot] = xRoot
        else:
            self.parents[xRoot] = yRoot
            if self.size[xRoot] == self.size[yRoot]:
                self.size[yRoot]+=1

N,M = list(map(int,input().split()))
tree = UnionFind(N)
P = list(map(int,input().split()))
for _ in range(M):
    x,y = list(map(int,input().split()))
    tree.union(x,y)

indeces = {}
indeces2 = {}
for i in range(N):
    indeces[P[i]]=i+1
    indeces2[i+1]=P[i]

group = {}
group2 = {}
for i in range(1,N+1):
    r = tree.find(i)
    if r not in group:
        group[r]=set()
    group[r].add(i)
    group2[i]=r

ans = 0
for n,index in list(indeces.items()):
    if n == index:
        ans += 1
    else:
        groupNum = group2[index]
        if n in group[groupNum]:
            ans += 1
            a = indeces2[n] #n番目に現在君臨している数字
            indeces2[n] = n
            indeces2[index] = a
            indeces[a] = index
            indeces[n] = n

print(ans)
# Original solution
#各pは、自分の今いるインデックスがindex p-1と繋がっていればそこに移動する
import sys
sys.setrecursionlimit(200000)

class UnionFind():
    def __init__(self,n):
        self.n=n
        self.parents = [i for i in range(n+1)]
        self.size = [1]*(n+1)
    def find(self,x):
        if self.parents[x]==x:
            return x
        else:
            self.parents[x]=self.find(self.parents[x])
            return self.parents[x]
    def unite(self,x,y):
        xRoot = self.find(x)
        yRoot = self.find(y)
        if xRoot == yRoot:
            return
        if self.size[xRoot]>self.size[yRoot]:
            self.parents[yRoot] = xRoot
        else:
            self.parents[xRoot] = yRoot
            if self.size[xRoot] == self.size[yRoot]:
                self.size[yRoot]+=1
N,M = list(map(int,input().split()))
P = list(map(int,input().split()))
tree = UnionFind(N)
for _ in range(M):
    x,y = list(map(int,input().split()))
    tree.unite(x,y)

count = 0
for i in range(N):
    if tree.find(i+1) == tree.find(P[i]):
        count += 1

print(count)

# Optimized solution
"""
初期状態でpiにいる数が、pi番目にたどり着けるかを判定すればよい。
unionFind木が使える
"""
N,M = list(map(int,input().split()))
P = list(map(int,input().split()))
class UnionFind():
    def __init__(self,n):
        self.n=n
        self.parents = [i for i in range(n+1)]
        self.size = [1]*(n+1)
    def find(self,x):
        if self.parents[x]==x:
            return x
        else:
            self.parents[x]=self.find(self.parents[x])
            return self.parents[x]
    def unite(self,x,y):
        xRoot = self.find(x)
        yRoot = self.find(y)
        if xRoot == yRoot:
            return
        if self.size[xRoot]>self.size[yRoot]:
            self.parents[yRoot] = xRoot
            self.size[xRoot] += self.size[yRoot]
            self.size[yRoot] = 0
        else:
            self.parents[xRoot] = yRoot
            self.size[yRoot] += self.size[xRoot]
            self.size[xRoot] = 0
tree = UnionFind(N)
for _ in range(M):
    x,y = list(map(int,input().split()))
    tree.unite(x,y)
cnt = 0
for i in range(N):
    p = P[i]
    if tree.find(i+1)==tree.find(p):
        cnt += 1

print(cnt)
# Original solution
N,M=list(map(int, input().split()))
p=[set()]+[set([int(x)]) for x in input().split()]
xy=[list(map(int, input().split())) for _ in range(M)]

for _ in range(10):
	for x,y in xy:
		p[x]=p[y]=p[x]|p[y]

print((sum([1 if i in s else 0 for (i, s) in enumerate(p)])))


# Optimized solution
N,M=list(map(int, input().split()))
p=list(map(int, input().split()))

uf=[i for i in range(N+1)]

def find(n):
	if uf[n] == n:
		return n
	uf[n] = find(uf[n])
	return uf[n]

def union(n, m):
	uf[find(n)] = find(m)

def same(n, m):
	return find(n) == find(m)

for _ in range(M):
	union(*list(map(int, input().split())))

for i in range(N+1):
	find(i)

print((sum([1 if same(i+1,v) else 0 for i,v in enumerate(p)])))
# Original solution
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def all_group_members(self):
        return [set(self.members(r)) for r in self.roots()]

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

def main():
    n, m = list(map(int, input().split()))
    P = {i : int(p) - 1 for i, p in enumerate(input().split())}
    uf = UnionFind(n)
    for _ in range(m):
        x, y = [int(x) - 1 for x in input().split()]
        uf.union(x, y)
    ans = 0
    for g in uf.all_group_members():
        Q = set([P[p] for p in g])
        ans += len(g & Q)
    print(ans)

if __name__ == '__main__':
    main()


# Optimized solution
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def all_group_members(self):
        return [set(self.members(r)) for r in self.roots()]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

def main():
    n, m = list(map(int, input().split()))
    P = list([int(x) - 1 for x in input().split()])
    uf = UnionFind(n)
    for _ in range(m):
        x, y = [int(x) - 1 for x in input().split()]
        uf.union(x, y)
    ans = 0
    for i, p in enumerate(P):
        if uf.same(i, p):
            ans += 1
    print(ans)

if __name__ == '__main__':
    main()
# Original solution
import sys

sys.setrecursionlimit(6500)

def find(n):
    if d[n]<0:
        return n
    else:
        d[n]=find(d[n])
        return d[n]

def union(a,b):
    a=find(a)
    b=find(b)
    if a==b:return False
    if d[a]<=d[b]:
        d[a]+=d[b]
        d[b]=a
    else:
        d[b]+=d[a]
        d[a]=b
    return True

def members(n):
    p=find(n)
    ans=[]
    for i in range(N):
        if find(i)==p:
            ans.append(i)
    return ans

N,M=list(map(int,input().split()))
p=list(map(int,input().split()))

d=[-1]*N

for i in range(M):
    x,y=list(map(int,input().split()))
    x,y=x-1,y-1
    union(x,y)

LN=[-1]*N
lis=[]
idx=0
for i in range(N):
    if LN[i]==-1:
        temp=members(i)
        l=[]
        for j in temp:
            LN[j]=idx
            l.append(p[j])
        lis.append(l)
        idx+=1

ans=0
for i in range(N):
    for j in lis[LN[i]]:
        if i+1==j:
            ans+=1
            lis[LN[i]].remove(i+1)
            break
print(ans)

# Optimized solution
import sys

sys.setrecursionlimit(6500)

def find(n):
    if d[n]<0:
        return n
    else:
        d[n]=find(d[n])
        return d[n]

def union(a,b):
    a=find(a)
    b=find(b)
    if a==b:return False
    if d[a]<=d[b]:
        d[a]+=d[b]
        d[b]=a
    else:
        d[b]+=d[a]
        d[a]=b
    return True

def members(n):
    p=find(n)
    ans=[]
    for i in range(N):
        if find(i)==p:
            ans.append(i)
    return ans

def same(a,b):
    if find(a)==find(b):return True
    else:return False

N,M=list(map(int,input().split()))
p=list(map(int,input().split()))

d=[-1]*N

for i in range(M):
    x,y=list(map(int,input().split()))
    x,y=x-1,y-1
    union(x,y)

ans=0
for i in range(N):
    if same(i,p[i]-1):
        ans+=1
print(ans)
# Original solution
class UF_tree:
    def __init__(self, n):
        self.root = [-1] * (n + 1)  # -1ならそのノードが根,で絶対値が木の要素数
        self.rank = [0] * (n + 1)

    def find(self, x):  # xの根となる要素番号を返す
        if self.root[x] < 0:
            return x
        else:
            self.root[x] = self.find(self.root[x])
            return self.root[x]

    def isSame(self, x, y):
        return self.find(x) == self.find(y)

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        elif self.rank[x] < self.rank[y]:
            self.root[y] += self.root[x]
            self.root[x] = y
        else:
            self.root[x] += self.root[y]
            self.root[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    def getNodeLen(self, x):
        return -self.root[self.find(x)]


if __name__ == "__main__":
    N, M = list(map(int, input().split()))
    P = list(map(int, input().split()))
    uf = UF_tree(2*N)
    for i, p in enumerate(P, start=1):
        uf.unite(i, p + N)

    for _ in range(M):
        x, y = list(map(int, input().split()))
        uf.unite(x + N, y + N)

    ans = 0
    for i in range(1, N + 1):
        if uf.isSame(i, i + N):
            ans += 1
    print(ans)


# Optimized solution
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)


class UF_tree:
    def __init__(self, n):
        self.root = [-1] * (n + 1)  # -1ならそのノードが根,で絶対値が木の要素数
        self.rank = [0] * (n + 1)

    def find(self, x):  # xの根となる要素番号を返す
        if self.root[x] < 0:
            return x
        else:
            self.root[x] = self.find(self.root[x])
            return self.root[x]

    def isSame(self, x, y):
        return self.find(x) == self.find(y)

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        elif self.rank[x] < self.rank[y]:
            self.root[y] += self.root[x]
            self.root[x] = y
        else:
            self.root[x] += self.root[y]
            self.root[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    def getNodeLen(self, x):
        return -self.root[self.find(x)]


if __name__ == "__main__":
    N, M = list(map(int, input().split()))
    P = list(map(int, input().split()))
    uf = UF_tree(N + 10)
    for _ in range(M):
        x, y = list(map(int, input().split()))
        uf.unite(x, y)

    ans = sum(uf.isSame(i, p) for i, p in enumerate(P, start=1))
    print(ans)
# Original solution
from operator import itemgetter
n=int(eval(input()))
l=[list(map(int,input().split())) for i in range(n)]
for i in range(n):
  l[i].sort()

ans=[]
l.sort()
B1=[];R1=[]
for i in range(n):
  B1.append(max(l[i]))
  R1.append(min(l[i]))
ans.append((max(B1)-min(B1))*(max(R1)-min(R1)))

Bleft=[]
Bright=[]
Rleft=[]
Rright=[]

M=B1[0];m=B1[0]
Bleft.append([m,M])
for i in range(1,n):
  M=max(M,B1[i])
  m=min(m,B1[i])
  Bleft.append([m,M])

B1.reverse()
M=B1[0];m=B1[0]
Bright.append([m,M])
for i in range(1,n):
  M=max(M,B1[i])
  m=min(m,B1[i])
  Bright.append([m,M])

M=R1[0];m=R1[0]
Rleft.append([m,M])
for i in range(1,n):
  M=max(M,R1[i])
  m=min(m,R1[i])
  Rleft.append([m,M])

R1.reverse()
M=R1[0];m=R1[0]
Rright.append([m,M])
for i in range(1,n):
  M=max(M,R1[i])
  m=min(m,R1[i])
  Rright.append([m,M])

for i in range(n-1):
  M1=max(Bleft[i][1],Rright[n-2-i][1])
  m1=min(Bleft[i][0],Rright[n-2-i][0])
  M2=max(Rleft[i][1],Bright[n-2-i][1])
  m2=min(Rleft[i][0],Bright[n-2-i][0])
  ans.append((M1-m1)*(M2-m2))

print((min(ans)))

# Optimized solution
import sys
input=sys.stdin.readline
n=int(eval(input()))
l=[list(map(int,input().split())) for i in range(n)]
for i in range(n):
  l[i].sort()

ans=[]
l.sort()
B1=[];R1=[]
for i in range(n):
  B1.append(max(l[i]))
  R1.append(min(l[i]))
ans.append((max(B1)-min(B1))*(max(R1)-min(R1)))

Bleft=[]
Bright=[]
Rleft=[]
Rright=[]

M=B1[0];m=B1[0]
Bleft.append([m,M])
for i in range(1,n):
  M=max(M,B1[i])
  m=min(m,B1[i])
  Bleft.append([m,M])

B1.reverse()
M=B1[0];m=B1[0]
Bright.append([m,M])
for i in range(1,n):
  M=max(M,B1[i])
  m=min(m,B1[i])
  Bright.append([m,M])

M=R1[0];m=R1[0]
Rleft.append([m,M])
for i in range(1,n):
  M=max(M,R1[i])
  m=min(m,R1[i])
  Rleft.append([m,M])

R1.reverse()
M=R1[0];m=R1[0]
Rright.append([m,M])
for i in range(1,n):
  M=max(M,R1[i])
  m=min(m,R1[i])
  Rright.append([m,M])

for i in range(n-1):
  M1=max(Bleft[i][1],Rright[n-2-i][1])
  m1=min(Bleft[i][0],Rright[n-2-i][0])
  M2=max(Rleft[i][1],Bright[n-2-i][1])
  m2=min(Rleft[i][0],Bright[n-2-i][0])
  ans.append((M1-m1)*(M2-m2))

print((min(ans)))
# Original solution
N = int(eval(input()))
xmin = ymin = float('inf')
xmax = ymax = 0
p = []
for i in range(N):
    x,y = list(map(int, input().split()))
    if x > y : 
        x,y= y,x
    p.append((x, y))
    if x < xmin:
        xmin = x
    elif x > xmax:
        xmax = x
    if y < ymin:
        ymin = y
    elif y > ymax:
        ymax = y
ret = (ymax-ymin) * (xmax-xmin)


p.sort()
dx = p[-1][0] - p[0][0]
ymin = p[0][0]
tymin = float('inf')
tymax = 0
for i in range(N-1):
    # print(i, dx, (xmax, xmin), end=' ==> ')
    tymin = min(tymin, p[i][1])
    xmax = max(xmax, p[i][1])
    xmin = min(tymin, p[i+1][0])
    dx = min(dx, xmax - xmin)
    # print(i, dx, (xmax, xmin))

# print(ret, (ymax-ymin) * (xmax-xmin) ,(ymax,ymin), (xmax,xmin), dx)
print((min(ret, (ymax-ymin) * dx)))




# Optimized solution
N = int(eval(input()))
xmin = ymin = float('inf')
xmax = ymax = 0
p = []
for i in range(N):
    x,y = list(map(int, input().split()))
    if x > y : 
        x,y= y,x
    p.append((x, y))
    if x < xmin:
        xmin = x
    elif x > xmax:
        xmax = x
    if y < ymin:
        ymin = y
    elif y > ymax:
        ymax = y
ret = (ymax-ymin) * (xmax-xmin)


p.sort()
dx = p[-1][0] - p[0][0]
ymin = p[0][0]
tymin = float('inf')
for i in range(N-1):
    # print(i, dx, (xmax, xmin), end=' ==> ')
    tymin = min(tymin, p[i][1])
    xmax = max(xmax, p[i][1])
    xmin = min(tymin, p[i+1][0])
    dx = min(dx, xmax - xmin)
    if tymin < p[i+1][0]:
        break
    # print(i, dx, (xmax, xmin))

print((min(ret, (ymax-ymin) * dx)))
# Original solution
#!/usr/bin/env python3
import sys
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
read = sys.stdin.buffer.read
sys.setrecursionlimit(10 ** 7)
INF = float('inf')

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

# どこで反転するかを記録する
pre = [0] * N
pre_index = 0
old_a = A[0]
if A[0] > A[1]:
    old_coef = -1
elif A[0] < A[1]:
    old_coef = 1
else:
    old_coef = 0

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

shojikin = 1000
stock = 0
if A[0] < A[pre[0]]:
    q, mod = divmod(shojikin, A[0])
    stock += q
    shojikin = mod
elif pre[0] == N - 1:
    # 何もしないほうが良い場合
    print('1000')
    quit()

# print("1st shojikin: {} stock: {}".format(shojikin, stock))

pre = list(set(pre))
pre.sort()
# print("sorted: {}".format(pre))
for deal_index in pre:
    if stock:
        shojikin += stock * A[deal_index]
        stock = 0
        # print("uri deal: {} shojikin: {} stock: {}".format(deal_index, shojikin, stock))
    else:
        q, mod = divmod(shojikin, A[deal_index])
        stock += q
        shojikin = mod
        # print("kai deal: {} shojikin: {} stock: {}".format(deal_index, shojikin, stock))
# 下がり続けた場合は払い戻し
if stock:
    shojikin += stock * A[deal_index]
    stock = 0
print(shojikin)

# Optimized solution
#!/usr/bin/env python3
import sys
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
read = sys.stdin.buffer.read
sys.setrecursionlimit(10 ** 7)
INF = float('inf')

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

shojikin = 1000
stock = 0
for i in range(N):
    if stock:
        shojikin += stock * A[i]
        stock = 0
    if i+1 < N:
        if A[i] < A[i+1]:
            q, mod = divmod(shojikin, A[i])
            stock = q
            shojikin = mod

print(shojikin)
# Original solution
N = int(eval(input()))
A = list(map(int,input().split()))
# print('A:',A)

from itertools import product
a=[0,1]  #0:buy  1:sell
Ls = list(product(a, repeat=N-1))
# print('Ls:',Ls)

out=0
for L in Ls:
    # print('L:',L)
    money=1000
    kabu=0
    for i in range(N-1):
        if L[i]==0:
            kabu+=money // A[i]
            money=money % A[i]

        else:
            money+=kabu*A[i]
            kabu=0
        # print('money,kabu:',money,kabu)
    money+=kabu*A[N-1]  #last
    out=max(out,money)

print(out)


# Optimized solution
N = int(eval(input()))
A = list(map(int,input().split()))
# print('A:',A)
money=1000
kabu=0

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

print(money)