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

from collections import deque


class dfs():
    
    def __init__(self, n, el):
        self.n = n
        self.el = el

        self.evenl = [0 for i in range(n)]
        #self.neibors = dict([(i,[]) for i in range(n)])
        self.neibors = [[] for i in range(n)]


    def calc(self, nf):
        used = []
        used.append( nf )
        stack = deque([ nf ])
        while( len(stack) != 0 ):
            current = stack.popleft()
            current_dist = self.evenl[current]

            for neibor in self.neibors[current]:
                neibor_n, neibor_w = neibor
                if neibor_n not in used:
                    used.append( neibor_n )
                    stack.append( neibor_n )
                    self.evenl[neibor_n] = self.xor( neibor_w, current_dist )                        

    def xor(self, x1,x2):
        return (x1 + x2) % 2

    def set_neibors(self):
        for e in self.el:
            u,v,w = e
            self.neibors[u-1].append( (v-1,w%2) )
            self.neibors[v-1].append( (u-1,w%2) )


n = int(input())
el = []
for i in range(n-1):
    u,v,w = map( int, input().split() )
    el.append( (u,v,w) )    

m = dfs(n,el)
m.set_neibors()
m.calc(0)

for item in m.evenl:
    print(item)

### FIXED CODE ###

from collections import deque

n = int(input())
neibors = [[] for i in range(n)]
for i in range(n-1):
    u,v,w = map( int, input().split() )
    neibors[u-1].append( (v-1,w%2) )
    neibors[v-1].append( (u-1,w%2) )

dist = [-1 for i in range(n)]
stack = deque([0])
while( len(stack) != 0 ):
    current = stack.popleft()
    current_dist = dist[current]

    for neibor_n, neibor_w in neibors[current]:
        if dist[neibor_n] == -1:
            stack.append( neibor_n )
            dist[neibor_n] = (neibor_w + current_dist) % 2  

for item in dist:
    print(item)
### BUGGY CODE ###

#N　展望台の数　M　道の数
N,M = map(int, input().split())
#高さ
H =list(map(int,input().split()))

ans=0

#道
J=[""]*M
for i in range(M):
  J[i]=(list(map(int, input().split())))

for i in range(1,N+1):
  dic={}
  flg = 0
  for j in J:    
    if j[0] == i:
      dic.setdefault(j[1],0)
      dic[j[1]]+=1 
    elif j[1] == i:
      dic.setdefault(j[0],0)
      dic[j[0]]+=1
  
  if len(dic) == 0:
    ans+=1
  else:
    for k,v in dic.items():
      if H[k-1] >= H[i-1]:
        flg = 1
    if flg == 0:
      ans+=1

    
print(ans)
    
#    for k,v in dic.items():
#      if not v > 1:
#        if H[k-1] >= H[i-1]:
#          flg = 1
#    if flg == 0:
#      ans.append(i)

  

### FIXED CODE ###

#N　展望台の数　M　道の数
N,M = map(int, input().split())
#高さ
H =list(map(int,input().split()))

ans=0
di = {}
#道
J=[""]*M
for i in range(M):
  a,b=list(map(int, input().split()))
  di.setdefault(a,[])
  di[a].append(b)
  di.setdefault(b,[])
  di[b].append(a)
  
#  J[i]=(list(map(int, input().split())))

for i in range(1,N+1):
  flg = 0

  if i in di.keys():
#    print(i)
#    print(di[i])
    for k in di[i]:
      if H[k-1] >= H[i-1]:
        flg = 1
    if flg == 0:
      ans+=1

  else:
    ans+=1

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

# これはエスパーですがMが素数ならNが何であってもできなさそう？未証明
# で 合成数のみっぽいので定石的に素因数分解すると
# 各項に因数をどれだけ割り振れるかみたいになる？
# -> サンプル1をみるとならなそう
# 最大公約数をgcdとすると、a*gcd*(N-1)+b*gcd = M となるのが都合よさそう こうなると右辺もgcdで割れるのでやはり約数のどれかになりそう
import math
n, m = map(int, input().split())


# 適当にググってコピペしただけの素数判定
def is_prime_2(num):
    if num < 2:
        return False
    if num == 2 or num == 3 or num == 5:
        return True
    if num % 2 == 0 or num % 3 == 0 or num % 5 == 0:
        return False

    # 疑似素数(2でも3でも5でも割り切れない数字)で次々に割っていく
    prime = 7
    step = 4
    num_sqrt = math.sqrt(num)
    while prime <= num_sqrt:
        if num % prime == 0:
            return False
        prime += step
        step = 6 - step

    return True


if is_prime_2(m):
    print(1)
    exit()

if m % n == 0:
    print(m // n)
    exit()
else:
    x = m // n
    for i in range(x, 0, -1):
        if m % i == 0:
            print(i)
            exit()
print(1)

### FIXED CODE ###

# これはエスパーですがMが素数ならNが何であってもできなさそう？未証明
# で 合成数のみっぽいので定石的に素因数分解すると
# 各項に因数をどれだけ割り振れるかみたいになる？
# -> サンプル1をみるとならなそう
# 最大公約数をgcdとすると、a*gcd*(N-1)+b*gcd = M となるのが都合よさそう こうなると右辺もgcdで割れるのでやはり約数のどれかになりそう
n, m = map(int, input().split())


def make_divisors(n):
    lower_divisors = []
    upper_divisors = []
    for i in range(1, int(n**0.5) + 1):
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n // i)

    upper_divisors.reverse()
    return lower_divisors + upper_divisors


if m % n == 0:
    print(m // n)
    exit()
else:
    x = m // n
    divisors = make_divisors(m)[::-1]
    for d in divisors:
        if d <= x:
            print(d)
            exit()
### BUGGY CODE ###

import math
import sys

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

def prime(i):
  k=[]
  maxi=i**0.5
  j=2
  moto=i
  while i>1:
    if i%j==0:
      k.append(j)
      i/=j
      j=2
    else:
      j+=1
  k.append(1)
  k=list(set(k))
  return k

a=set(prime(M[0]))
b=set(prime(M[1]))
print(len(list(a&b)))

### FIXED CODE ###

import math
import sys

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


def prime(i):
  k=[]
  num=i
  j=2
  while j*j<=num:
    if i%j==0:
      i//=j
      k.append(j)
    else:
      j+=1
  if i!=1:
    k.append(i)
  k.append(1)
  return k

a=set(prime(M[0]))
b=set(prime(M[1]))
print(len(list(a&b)))
### BUGGY CODE ###

import copy

n = int(input())
x = list(map(int,input().split()))
base = copy.deepcopy(x)
base_1 = copy.deepcopy(x)
base.sort()
base_1.sort()

for i in range(n):
  a_l = base.index(x[i])
  a_u = base_1.index(x[i])
  
  if a_l == (n-1)-a_u:
    if n//2 > a_l:
      ans = base[n//2]
    elif n//2 <= a_l:
      ans = base[n//2-1]
      
  else:
    if (a_l <= n//2-1) and (n//2 <= a_u):
      ans = base[a_l]
    elif a_u <= n//2 - 1:
      ans = base[n//2]
    elif n//2 <= a_l:
      ans = base[n//2 - 1]
      
  print(ans)

### FIXED CODE ###

import copy

n = int(input())
x = list(map(int,input().split()))
key = {}
base = copy.deepcopy(x)
base.sort()

for i in range(n):

  if n//2 > i:
    ans = base[n//2]
  elif n//2 <= i:
    ans = base[n//2-1]
   
  if not ("key" + str(base[i]) in key):
    key["key" + str(base[i])] = ans
    
for i in range(n):
  print(key["key" + str(x[i])])
### BUGGY CODE ###

import bisect
while True:
    N,M=map(int,raw_input().split())
    if N==M==0:break
    L=[input() for i in range(N)]
    L.append(0)
    S=set(i+j for i in L for j in L)
    B=sorted(S)
    maxInt=0
    for i in B:
        if i>M:break
        idx=bisect.bisect(B,M-i)
        maxInt=max(maxInt,i+B[idx-1])
    print maxInt

### FIXED CODE ###

import bisect
while True:
    N,M=map(int,raw_input().split())
    if N==M==0:break
    L=[input() for i in range(N)]
    L.append(0)
    S=set(i+j for i in L for j in L)
    B=sorted(S)
    t=bisect.bisect(B,M)-1
    maxInt=max(i+B[bisect.bisect(B,M-i)-1] for i in B[:t])
    print maxInt
### BUGGY CODE ###

n, *a = map(int, open(0).read().split())

for i in range(1,n+1):
    print(a.count(i))

### FIXED CODE ###

import collections

n, *a = map(int, open(0).read().split())

l = collections.Counter(a)

for i in range(1,n+1):
    if l[i]:
        print(l[i])
    else:
        print(0)
### BUGGY CODE ###

def p_e():
    N = int(input())
    # A = [int(input()) for _ in range(N)]
    ans = [-1]

    for _ in range(N):
        a = int(input())
        is_set = False
        for i, l in enumerate(ans):
            if l < a:
                ans[i] = a
                is_set = True
                break

        if not is_set:
            ans.append(a)

    print(len(ans))


if __name__ == '__main__':
    p_e()


### FIXED CODE ###

from bisect import *


def p_e():
    N = int(input())
    # A = [int(input()) for _ in range(N)]
    ans = [-1] * N

    for _ in range(N):
        a = int(input())
        ans[bisect(ans, a - 1) - 1] = a

    print(N - bisect(ans, -1))


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

N,M=map(int,input().split())
d={}
for i in range(M):d[i]=[0]
for i in range(N):
    a,b=map(int,input().split())
    if 0<=M-a:
        d[M-a].append(b)

t=[]
ans=0
for i in range(M)[::-1]:
    t+=d[i]
    ans+=max(t)
    t.remove(max(t))
print(ans)

### FIXED CODE ###

import heapq

N,M=map(int,input().split())
d={}
for i in range(M):d[i]=[0]
for i in range(N):
    a,b=map(int,input().split())
    if 0<=M-a:
        d[M-a].append(b)

hq=[]
ans=0
for i in range(M)[::-1]:
    [heapq.heappush(hq,-j) for j in d[i]]
    ans-=heapq.heappop(hq)
print(ans)
### BUGGY CODE ###

from collections import deque
n = int(input())
path = [[] for _ in range(n)]
ab = []
color = [0]*(n-1)
for i in range(n-1):
  a,b = map(int,input().split())
  a -= 1
  b -= 1
  ab.append([a,b])
  path[a].append(b)
  path[b].append(a)
  
que = deque()
que.append((0,0))
reached = [False]*n
reached[0] = True
while que:
  p,pc = que.popleft()
  c = 0
  for i in path[p]:
    if reached[i] == False:
      while True:
        c += 1
        if c == pc:continue
        color[ab.index(sorted([p,i]))] = c
        break
      reached[i] = True
      que.append((i,c))
print(max(color))
for i in color:
  print(i)


### FIXED CODE ###

from collections import deque
n = int(input())
path = [[] for _ in range(n)]
ab = []
color = {}
for i in range(n-1):
  a,b = map(int,input().split())
  a -= 1
  b -= 1
  ab.append((a,b))
  path[a].append(b)
  path[b].append(a)
  
que = deque()
que.append((0,0))
reached = [False]*n
reached[0] = True
while que:
  p,pc = que.popleft()
  c = 0
  for i in path[p]:
    if reached[i] == False:
      while True:
        c += 1
        if c == pc:continue
        color[tuple(sorted((p,i)))] = c
        break
      reached[i] = True
      que.append((i,c))
print(max(color.values()))
for i in ab:
  print(color[i])
### BUGGY CODE ###

import sys
input = sys.stdin.readline
 
H, W, M = map(int, input().split())
Hsum = [0] * H
Wsum = [0] * W
hw = set()
for m in range(M):
  h, w = map(int, input().split())
  Hsum[h-1] += 1
  Wsum[w-1] += 1
  hw.add((h-1, w-1))

hcnt = Hsum.count(max(Hsum))
wcnt = Wsum.count(max(Wsum))
if hcnt * wcnt > M:
  print(max(Hsum) + max(Wsum))
  sys.exit()

hidx = [i for i, _ in enumerate(Hsum) if _ == max(Hsum)]
widx = [i for i, _ in enumerate(Wsum) if _ == max(Wsum)]
for h in hidx:
  for w in widx:
    if (h, w) not in hw:
      print(max(Hsum) + max(Wsum))
      sys.exit()
print(max(Hsum) + max(Wsum) - 1)

### FIXED CODE ###

import sys
input = sys.stdin.readline
 
H, W, M = map(int, input().split())
Hsum = [0] * H
Wsum = [0] * W
hw = set()
for m in range(M):
  h, w = map(lambda x: int(x) - 1, input().split())
  Hsum[h] += 1
  Wsum[w] += 1
  hw.add((h, w))

mh = max(Hsum)
mw = max(Wsum)
hidx = [i for i, _ in enumerate(Hsum) if _ == mh]
widx = [i for i, _ in enumerate(Wsum) if _ == mw]
 
if len(hidx) * len(widx) > M:
  print(mh + mw)
else:
  fi_flg = False
  for h in hidx:
    for w in widx:
      if (h, w) not in hw:
        print(mh + mw)
        fi_flg = True
        break
    if fi_flg:
      break
  if fi_flg is False:
    print(mh + mw - 1)
### BUGGY CODE ###

n,k=map(int,input().split())
a=list(map(int,input().split()))
dict={}
for i in range(n):
    dict[i]=a[i]-1 #i番目の町からどこにつくか
tmp=0#現在知
num2city={}
city2num={}
city2num[0]=0#どのまちが何回目か
num2city[0]=0#j回目にどこにいるか
for j in range(1,k+1):
    if tmp==dict[tmp]:
        break
    tmp=dict[tmp]#現在地更新
    if tmp not in num2city.values():#現在地がまだきたことない
        num2city[j]=tmp
        city2num[tmp]=j
    else:
        mae=city2num[tmp]
        term=j-mae 
        res=k-j
        r=res%term
  #      print(mae,term,res,r,mae+r,num2city[mae+r])
        tmp=num2city[mae+r]
 #       print(tmp)
        break
   # print(tmp+1)
    
#print(num2city)
#print(city2num)
print(tmp+1)



### FIXED CODE ###

n,k=map(int,input().split())
a=list(map(int,input().split()))
dict={}
for i in range(n):
    dict[i]=a[i]-1 #i番目の町からどこにつくか
tmp=0#現在知
num2city={}
city2num={}
city2num[0]=0#どのまちが何回目か
num2city[0]=0#j回目にどこにいるか
alre=[-1]*n
alre[0]=1
for j in range(1,k+1):
    if tmp==dict[tmp]:
        break
    tmp=dict[tmp]#現在地更新
    if alre[tmp]==-1:#tmp not in num2city.values():#現在地がまだきたことない
        alre[tmp]=1
        num2city[j]=tmp
        city2num[tmp]=j
    else:
        mae=city2num[tmp]
        term=j-mae 
        res=k-j
        r=res%term
  #      print(mae,term,res,r,mae+r,num2city[mae+r])
        tmp=num2city[mae+r]
 #       print(tmp)
        break
   # print(tmp+1)
    
#print(num2city)
#print(city2num)
print(tmp+1)
### BUGGY CODE ###

N, K = map(int,input().split())
p = list(map(int,input().split()))
c = list(map(int,input().split()))
K = K-1
ans = -10**9-1
for h in range(N):
   i = h+1
   start = i
   circle = [c[i-1]]
   i = p[i-1]
   while i != start:
      score = circle[-1] + c[i-1]
      circle.append(score)
      i = p[i-1]
   l=len(circle)
   for j in range(min(l, K+1)):
      if circle[l-1] > 0:
         score = circle[j] + ((K - j)//l)*circle[l-1]
      else:
         score = circle[j]
      ans = max(score, ans)      
print(ans)

### FIXED CODE ###

N, K = map(int,input().split())
p = list(map(int,input().split()))
c = list(map(int,input().split()))
K = K-1
ans = -10**9-1
for h in range(N):
   i = h+1
   start = i
   circle = [c[i-1]]
   i = p[i-1]
   while i != start:
      score = circle[-1] + c[i-1]
      circle.append(score)
      i = p[i-1]
   l=len(circle)
   for j in range(min(l, K+1)):
      if circle[l-1] > 0:
         score = circle[j] + ((K - j)//l)*circle[l-1]
      else:
         score = circle[j]
      ans = max(score, ans)      
print(ans)
### BUGGY CODE ###

# -*- coding: utf-8 -*-

class HashTable(list):
    def __init__(self, length):
        list.__init__(self)
        self.length = length
        self[:] = [None] * length

    def h1(self, key):
        return key % self.length

    def h2(self, key):
        return 1 + (key % (self.length - 1))

    def h(self, key, i):
        return (self.h1(key) + i*self.h2(key)) % self.length

    def insert(self, key):
        i = 0
        while True:
            j = self.h(key, i)
            if self[j] is None:
                self[j] = key
                return j
            else:
                i += 1
    
    def search(self, key):
        i = 0
        while True:
            j = self.h(key, i)
            if self[j] == key:
                return j
            elif self[j] is None or i >= self.length:
                return None
            else:
                i += 1

def getNum(char):
    
    char2num = str.maketrans("ACGT", "1234")
    return int(char.translate(char2num), 5)

if __name__ == '__main__':

    n = int(input())
    T = HashTable(n*10)
    C = [input().split(" ") for i in range(n)]
    C = map(lambda x:(x[0], getNum(x[1])), C)
    
    for command, num in C:
        if command == "insert":
            T.insert(num)
        else:
            if T.search(num) is None:
                print("no")
            else:
                print("yes")



### FIXED CODE ###

# -*- coding: utf-8 -*-

class HashTable(list):
    def __init__(self, length):
        list.__init__(self)
        self.length = length
        self[:] = [None] * length

    def h(self, key, i):
        h1 = key % self.length
        h2 = 1 + (key % (self.length - 1))
        return (h1 + i*h2) % self.length

    def insert(self, key):
        i = 0
        while True:
            h1 = key % self.length
            h2 = 1 + (key % (self.length - 1))
            j = (h1 + i*h2) % self.length
            #j = self.h(key, i)
            if self[j] is None:
                self[j] = key
                return j
            else:
                i += 1
    
    def search(self, key):
        i = 0
        while True:
            h1 = key % self.length
            h2 = 1 + (key % (self.length - 1))
            j = (h1 + i*h2) % self.length
            #j = self.h(key, i)
            if self[j] == key:
                return j
            elif self[j] is None or i >= self.length:
                return None
            else:
                i += 1

def getNum(char):
    char2num = str.maketrans("ACGT", "1234")
    return int(char.translate(char2num), 5)

if __name__ == '__main__':

    n = int(input())
    T = HashTable(1046527)
    C = [input().split(" ") for i in range(n)]
    
    for command, char in C:
        num = getNum(char)
        if command[0] == "i":
            T.insert(num)
        else:
            if T.search(num) is None:
                print("no")
            else:
                print("yes")
### BUGGY CODE ###

import bisect as bi
N,M=map(int,input().split())
A=list(map(int,input().split()))
L=[]
for i in range(M):
    l=list(map(int,input().split()))
    L.append(l)
L=sorted(L,reverse=True,key=lambda x: x[1])
A=sorted(A)
x=[]
for i in range(M):
    if bi.bisect_left(A,L[i][1])==0:
        break
    if len(A)==0:
        break
    m=min(L[i][0],bi.bisect_left(A,L[i][1]))
    for l in range(m):
        A.pop(0)
        x.append(L[i][1])
print(sum(x)+sum(A))




### FIXED CODE ###

from operator import itemgetter
l = list(map(int, input().split()))
N = l[0]
M = l[1]
A = list(map(int, input().split()))
B = []
for i in range(M):
    b = list(map(int, input().split()))
    B.append(b)
A = sorted(A)
B = sorted(B, key=lambda x: x[1])
m = 0
s = 0
for i in range(M):
    i = M-1-i
    if B[i][0]+m <= N-1:

        if A[B[i][0]+m] <= B[i][1]:
            m = m+B[i][0]
            s += B[i][1]*B[i][0]
        else:
            if A[m] <= B[i][1]:
                for l in range(m, N):
                    if A[l] >= B[i][1]:
                        s += B[i][1]*(l-m)
                        m = l
                        break
            else:
                break
    else:
        if A[N-1] <= B[i][1]:
            s = s+B[i][1]*(N-m)
            m = N
            break
        else:
            if A[m] <= B[i][1]:
                for l in range(m, N):
                    if A[l] >= B[i][1]:
                        s += B[i][1]*(l-m)
                        m = l
                        break
            else:
                break
if m < N:
    for i in range(m, N):
        s += A[i]
print(s)
### BUGGY CODE ###

import sys
n = int(input())
road = [0]*n
for i in range(n):
  road[i] = [int(x) for x in input().split()]

road_judge = [[True]*n for i in range(n)]
for k in range(n):
  for i in range(n):
    for j in range(n):
      if road[i][j] > road[i][k]+road[k][j]:
        print(-1)
        sys.exit()
      if road[i][j] == road[i][k]+road[k][j] and i != k and j != k:
        road_judge[i][j] = False
ans = 0
for i in range(n):
  for j in range(n):
    if road_judge[i][j]:
      ans += road[i][j]
print(ans//2)

### FIXED CODE ###

import sys
n = int(input())
road = [0]*n
for i in range(n):
  road[i] = [int(x) for x in input().split()]

road_judge = [[True]*n for i in range(n)]
for k in range(n):
  for i in range(n):
    for j in range(n):
      if road[i][j] > road[i][k]+road[k][j]:
        print(-1)
        sys.exit()
      if road[i][j] == road[i][k]+road[k][j] and i != k and j != k:
        road_judge[i][j] = False
ans = 0
for i in range(n):
  for j in range(n):
    if road_judge[i][j]:
      ans += road[i][j]
print(ans//2)
### BUGGY CODE ###

N, Q = map(int,input().split())
S = input()
count = 0

for i in range(Q):
  l, r = map(int,input().split())
  Si = S[l-1:r]
  
  len_Si = len(Si)
  for i in range(len_Si-1):
    if Si[i:i+2] == 'AC':
      count += 1
  print(count)
  count = 0


### FIXED CODE ###

N, Q = map(int,input().split())
S = input()
t=[0]*(N+1)
for i in range(N):
  t[i + 1] = t[i] + (1 if S[i : i + 2] == 'AC' else 0)
for i in range(Q):
  l, r = map(int, input().split())
  print(t[r-1] - t[l-1])
### BUGGY CODE ###

# -*- coding: utf-8 -*-

def main():
     k = int(input())

     runrun = [1, 2, 3, 4, 5, 6, 7, 8, 9]
     count = 0
     while(len(runrun) < k):
          target = runrun[count]
          runrun = runrun + make(target)
          count += 1
          # print(runrun)

     print(runrun[k-1])

def make(n):
     num = n % 10
     if num == 0:
          return [n * 10 + num, n * 10 + num + 1]
     elif num == 9:
          return [n * 10 + num - 1, n * 10 + num]
     else:
          return [n * 10 + num - 1, n * 10 + num, n * 10 + num + 1]

if __name__ == "__main__":
    main()


### FIXED CODE ###

# -*- coding: utf-8 -*-

def main():
     k = int(input())

     runrun = [1, 2, 3, 4, 5, 6, 7, 8, 9]
     count = 0
     while(len(runrun) < k):
          target = runrun[count]
          num = target % 10
          if num != 0:
               runrun.append(target * 10 + num - 1)
          runrun.append(target * 10 + num)
          if num != 9:
               runrun.append(target * 10 + num + 1)

          count += 1
          # print(runrun)

     print(runrun[k-1])

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

def main():
    import sys
    input = sys.stdin.readline

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

    INF = 10 ** 9
    #入力

    # 入力は1-index
    # 内部で0-indexにして処理
    G = []
    for _ in range(M): #M個の辺の情報を受け取る
        A, B, C = map(int, input().split()) #lからrへ重みsの辺が存在
        G += [[A - 1, B - 1, P - C]] #有向グラフのときはここだけ

    check = [False] * N
    d = [INF] * N #距離を記録

    def shortest_path(s): #S番目の頂点から各頂点への最短距離を求める
        s -= 1
        d[s] = 0
        j = 0
        while j < N - 1:
            for i in range(M): #無向グラフのときは辺は実質的には2倍
                e = G[i]
                if d[e[0]] != INF and d[e[1]] > d[e[0]] + e[2]:
                    d[e[1]] = d[e[0]] + e[2]
            j += 1
        
        j = 0
        while j < N:
            for i in range(M):
                e = G[i]
                if d[e[0]] == INF:
                    continue
                if d[e[0]] != INF and d[e[1]] > d[e[0]] + e[2]:
                    d[e[1]] = d[e[0]] + e[2]
                    check[e[1]] = True
                if check[e[0]]:
                    check[e[1]] = True
            j += 1

    shortest_path(1)
    if check[N - 1]:
        print (-1)
    else:
        ans = d[N - 1]
        print (max(0, -ans))
    # print (d)

if __name__ == '__main__':
    main()

### FIXED CODE ###

#単一始点最短経路問題
#負の辺があっても動作する

#最短経路を求める
#計算量O(N * M)

INF = 10 ** 15
#入力
# N = int(input()) #頂点の数
# M = int(input()) #辺の数
N, M, P = map(int, input().split())

# 入力は1-index
# 内部で0-indexにして処理
G = []
for _ in range(M): #M個の辺の情報を受け取る
    l, r, s = map(int, input().split()) #lからrへ重みsの辺が存在
    G += [[l-1, r-1, -(s-P)]] #有向グラフのときはここだけ
    # G += [[r-1, l-1, s]] #無向グラフのときはこの行も必要


#メイン文
d = [0] * N #最短距離を記録しておくリスト
# prev = [-1] * N
def shortest_path(s): #S番目の頂点から各頂点への最短距離を求める
    s -= 1
    for i in range(N):
        d[i] = INF
    d[s] = 0
    count = 0
    while True:
        count += 1
        update = False
        for i in range(M): #無向グラフのときは辺は実質的には2倍
            e = G[i]
            if d[e[0]] != INF and d[e[1]] > d[e[0]] + e[2]:
                d[e[1]] = d[e[0]] + e[2]
                update = True
                # prev[e[1]] = e[0]
        if not update: #更新が終わったとき
            return True
        if count == N - 1: #永遠に更新が起きているとき
            tmp = d[N -1]
        if count == 2 * N:
            if d[N - 1] == tmp:
                return True #N-1の値が更新されていないとき
            else:
                return False #N + 2回目でもN - 1の値が小さくなっている-->得点が無限に大きくなる

#呼び出しスタート地点を入れる
if not shortest_path(1):
    print (-1)
    # print (d)
    exit()
# print (d)

print (max(0, -d[N - 1]))
### BUGGY CODE ###

import fractions
import functools


n = int(input())
a = [int(i) for i in input().split()]
ans = 0

for i in range(n):
    m = functools.reduce(fractions.gcd, a[:i] + a[i+1:])
    ans = max(ans, m)

print(ans)


### FIXED CODE ###

import fractions
import functools


n = int(input())
a = [int(i) for i in input().split()]
ans = 0

# a_0 ~ a_i の 最大公約数
l_gcd = [0]
l_append = l_gcd.append
# a_i ~ a_n-1 の最大公約数
r_gcd = []
r_append = r_gcd.append

for i, a_i in enumerate(a):
    if i == 0:
        l_append(a_i)
    else:
        l_append(fractions.gcd(a_i, l_gcd[i]))

for i, a_i in enumerate(reversed(a)):
    if i == 0:
        r_append(a_i)
    else:
        r_append(fractions.gcd(a_i, r_gcd[i-1]))
r_gcd.reverse()
r_append(0)

m = []
m_append = m.append
for i in range(n):
    m_append(fractions.gcd(l_gcd[i], r_gcd[i+1]))
ans = max(m)
print(ans)