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

n = int(input())
tree = [[0]*n for i in range(n)]
input_list = [0]*n
   
for i in range(n-1):
    a, b = map(int, input().split())
    input_list[i] = [a, b]
    tree[a-1][b-1] = -1
    tree[b-1][a-1] = -1

ans = 0
for i in range(n):
    key = tree[i].count(-1)
    if key > ans:
        ans = key
print(ans)

keyofkey = [[int(i) for i in range(1, ans+1)] for i in range(n)]

for i in range(n-1):
    a, b = input_list[i][0], input_list[i][1]
    key_list = list(set(keyofkey[a-1]) & set(keyofkey[b-1]))
    p = key_list[0]
    keyofkey[a-1].remove(p)
    keyofkey[b-1].remove(p)
    print(p)

### FIXED CODE ###

from collections import deque
import sys

def main():
    input = sys.stdin.readline
    n = int(input())
    
    node = [0]*(n-1)
    next_node = [[] for _ in range(n)]
    for i in range(n-1):
        a, b = map(int, input().split())
        node[i] = (a-1, b-1)
        next_node[a-1].append(b-1)
        next_node[b-1].append(a-1)
    
    ans = 0
    for i in range(n):
        if ans < len(next_node[i]):
            ans = len(next_node[i])
    print(ans)
    
    not_yet = deque([])
    already = [False]*n
    parent = [0]*n
    ans_list = dict()
    k = 1
    
    already[0] = True
    for value in next_node[0]:
        not_yet.append(value)
        ans_list[(0, value)] = k
        parent[value] = k
        already[value] = True
        k += 1
    
    
    while not_yet:
        k = 1
        key = not_yet.popleft()
        for value in next_node[key]:
            if already[value]:
                continue
            already[value] = True
            not_yet.append(value)
            if k == parent[key]:
                k += 1
            parent[value] = k
            p, q = min([key, value]), max([key, value])
            ans_list[(p, q)] = k
            k += 1
            
    
    for value in node:
        print(ans_list[value])


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

N = int(input())
S = list(input())
cnt = 0
cnt_1 = 0
for i in range(N) :
    for j in range(i,N) :
        for k in range(j,N) :
            cnt_1 += 1
            if ((S[i] == S[j]) or (S[i] == S[k]) or (S[j] == S[k])) or (j-i == k-j) :
                cnt += 1
print(cnt_1 - cnt)

### FIXED CODE ###

N = int(input())
S = list(input())
r,g,b = 0,0,0
k = 0
buf = 0

for i in range(N) :
    if S[i] == 'R' :
        r += 1
    elif S[i] == 'G' :
        g += 1
    else :
        b += 1

for j in range(N) :
    for i in range(j) :
        k = 2 * j - i
        if k <= N-1 :
            if S[i] != S[j] and S[i] != S[k] and S[j] != S[k] :
                buf += 1

print(r*g*b - buf)
### BUGGY CODE ###

from collections import deque
H, W = map(int, input().split())
G = [input() for _ in range(H)]
dist = [0]*(H*W)
B = deque()
geta = W
for i, g in enumerate(G):
    for j, f in enumerate(g):
        if f == '#':
            B.append(i*geta + j)
visited = set(B)
while B:
    dh, dw = divmod(B.pop(), geta)
    dhw = dh * geta + dw
    for di, dj in ((1, 0), (-1, 0), (0, 1), (0, -1)):
        ni, nj = dh + di, dw + dj
        if not (0 <= ni <= H - 1) or not (0 <= nj <= W - 1):
            continue
        nij = ni * geta + nj
        if nij in visited or G[ni][nj] == '#':
            continue
        visited.add(nij)
        dist[nij] = 1 + dist[dhw]
        B.appendleft(nij)
print(max(dist))

### FIXED CODE ###

from collections import deque
H, W = map(int, input().split())
G = [input() for _ in range(H)]
dist = [0]*(H*W)
bn = 0
B = deque()
geta = W
for i, g in enumerate(G):
    for j, f in enumerate(g):
        if f == '#':
            bn += 1
            B.append(i*geta + j)
visited = set(B)
while bn < H*W:
    if not B:
        break
    dh, dw = divmod(B.pop(), geta)
    dhw = dh * geta + dw
    for di, dj in ((1, 0), (-1, 0), (0, 1), (0, -1)):
        ni, nj = dh + di, dw + dj
        if not (0 <= ni <= H - 1) or not (0 <= nj <= W - 1):
            continue
        nij = ni * geta + nj
        if nij in visited or G[ni][nj] == '#':
            continue
        visited.add(nij)
        dist[nij] = 1 + dist[dhw]
        B.appendleft(nij)
print(max(dist))
### BUGGY CODE ###

MOD = 10**9+7
n, m = map(int, input().split())
a = [int(input()) for _ in range(m)]
dp = [0] * (n+1)
dp[0] = 1
for i in range(1, n+1):
    if i not in a:
        dp[i] = (dp[i-1] + dp[i-2]) % MOD
print(dp[n])


### FIXED CODE ###

MOD = 10**9+7
n, m = map(int, input().split())
A = [int(input()) for _ in range(m)]

safe = [True] * (n+1)
for a in A:
    safe[a] = False

dp = [0] * (n+1)
dp[0] = 1
for i in range(1, n+1):
    if safe[i]:
        dp[i] = (dp[i-1] + dp[i-2]) % MOD

print(dp[n])
### BUGGY CODE ###

a,b,k = map(int, input().split())
c = []
for x in range(a,b+1):
  if a <= x and a <= b:
    c.append(x)
c1 = []
for x in c[:k]:
  c1.append(x)
for x in c[(len(c)-k):]:
  if x not in c1:
    c1.append(x)
for x in c1:
  print(x)

### FIXED CODE ###

a,b,k = map(int, input().split())
ab = range(a, b+1)
for c in sorted(set(ab[:k])|set(ab[-k:])):
    print(c)
### BUGGY CODE ###

from  fractions  import gcd
n,m = map(int,input().split())
s = input()
t = input()
def lcm(x,y):
  return (x*y)//gcd(x,y)

a = lcm(n,m)
l = [0 for i in range(a)]
l1 = [0 for i in range(a)]
for i in range(n):
  l[int(i*(a/n))+1-1] = s[i]
for j in range(m):
  l1[int(j*(a/m))+1-1] = t[j]
for j,k in zip(l,l1):
  if j!=k and j!=0 and k!=0:
    print("-1")
    exit()
else:
  print(a)

### FIXED CODE ###

from  fractions  import gcd
n,m = map(int,input().split())
s = input()
t = input()
def lcm(x,y):
  return (x*y)//gcd(x,y)

a = lcm(n,m)
b = gcd(n,m)
if b==1:
  if s[0]==t[0]:
    print(a)
  else:
    print(-1)
else:
  k = int(a//b)
  for i in range(b):
    w = int(n*i//b)
    ww = int(m*i//b)
    if s[w]==t[ww]:
      continue
    else:
      print(-1)
      exit()
  else:
    print(a)
### BUGGY CODE ###

from itertools import permutations

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

ans = 0


def dfs(v):
    if len(v) == 2:
        global ans
        ans = max((v[0] + v[1]) / 2, ans)
        return 0
    for vv in permutations(v, 2):
        v_alche = v[:]
        v_alche.remove(vv[0])
        v_alche.remove(vv[1])
        v_alche.append((vv[0] + vv[1]) / 2)
        dfs(v_alche)


dfs(values)
print(ans)


### FIXED CODE ###

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

v.sort(reverse=True)

while len(v) > 1:
    v = v[:-2] + [(v[-1] + v[-2]) / 2]

print(v[0])
### BUGGY CODE ###

a,b,q = map(int,input().split())
A = []
B = []

for _ in range(a):
    A.append(int(input()))

for _ in range(b):
    B.append(int(input()))

def search(A,x):
    left =0
    right = len(A)-1
    
    if x<A[0]:
        return (float('inf'),0)
    if x >A[-1]:
        return (right,float('inf'))
    
    while left != right-1:
        center = (left+right)//2
        
        if A[center] > x:
            right = center
        else:
            left = center
    
    return (left,right)


def dist(A,x,lr):
    if lr == float('inf'):
        return float('inf')
    return abs(x - A[lr])

for _ in range(q):
    x = int(input())
    sl,sr = search(A,x)
    tl,tr = search(B,x)
    sl = dist(A,x,sl)
    sr = dist(A,x,sr)
    tl = dist(B,x,tl)
    tr = dist(B,x,tr)
    p1 = min(sl,sr)+min(tl,tr)+min(min(sl,sr),min(tl,tr))
    p2 = max(sl,tl)
    p3 = max(sr,tr)
    print(min(p1,p2,p3))

### FIXED CODE ###

import sys
readline = sys.stdin.readline


def main():
    a,b,q = map(int,readline().split())
    A = [int(readline()) for i in range(a)]
    B = [int(readline()) for i in range(b)]
    def search(A,x):
        left =0
        right = len(A)-1
        
        if x<A[0]:
            return (float('inf'),abs(x - A[left]))
        if x >A[-1]:
            return (abs(x - A[right]),float('inf'))
        
        while left != right-1:
            center = (left+right)//2
            
            if A[center] > x:
                right = center
            else:
                left = center
        
        return (abs(x - A[left]),abs(x - A[right]))
    
    
    def dist(A,x,lr):
        if lr == float('inf'):
            return float('inf')
        return abs(x - A[lr])
    
    for _ in range(q):
        x = int(readline())
        sl,sr = search(A,x)
        tl,tr = search(B,x)
        print(min(min(sl,sr)+min(tl,tr)+min(min(sl,sr),min(tl,tr)),max(sl,tl),max(sr,tr)))

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

import sys

# import re
import math
import collections
# import decimal
import bisect
import itertools
import fractions
# import functools
import copy
import heapq
import decimal
# import statistics
import queue

sys.setrecursionlimit(10000001)
INF = 10 ** 16
MOD = 10 ** 9 + 7

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===


def main():
    N = ni()
    lim = 3500

    for h in range(1, lim + 1):
        for n in range(1, lim + 1):
            up = N * h * n
            down = 4 * h * n - N * n - N * h
            if down != 0:
                if up % down == 0:
                    if 0 < up // down:
                        print(h, n, up // down)
                        exit(0)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys

# import re
import math
import collections
# import decimal
import bisect
import itertools
import fractions
# import functools
import copy
import heapq
import decimal
# import statistics
import queue

sys.setrecursionlimit(10000001)
INF = 10 ** 16
MOD = 10 ** 9 + 7

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===


def main():
    N = ni()
    lim = 3500

    for h in range(1, lim + 1):
        for n in range(1, lim + 1):
            up = N * h * n
            down = 4 * h * n - N * n - N * h
            if down != 0:
                if up % down == 0:
                    if 0 < up // down:
                        print(h, n, up // down)
                        exit(0)


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

# -*- coding: utf-8 -*-
N, M = map(int, input().split())

p_list = []
S_list = []
ac_list = []
wa_list = [0 for i in range(N)]
for i in range(M):
    p, S = map(str, input().split())
    p = int(p)
    if p not in ac_list:
        if S == "AC":
            ac_list.append(p)
        else:
            wa_list[p - 1] += 1

wa_num = 0
for i in range(len(ac_list)):
    wa_num += wa_list[ac_list[i] - 1]
print("{} {}".format(len(ac_list), wa_num))

### FIXED CODE ###

# -*- coding: utf-8 -*-
N, M = map(int, input().split())

p_list = []
S_list = []
ac_set = set([])
wa_list = [0 for i in range(N)]
for i in range(M):
    p, S = map(str, input().split())
    p = int(p)
    if p not in ac_set:
        if S == "AC":
            ac_set.add(p)
        else:
            wa_list[p - 1] += 1

wa_num = 0
for i in ac_set:
    wa_num += wa_list[i - 1]
print("{} {}".format(len(ac_set), wa_num))
### BUGGY CODE ###

import functools


@functools.lru_cache(maxsize=None)
def rec(state, v):
    if state == (1 << V) - 1 and v == 0:
        return 0
    ret = INF
    for i, w in enumerate(A[v]):
        if not (state >> i & 1):
            ret = min(ret, rec(state | 1 << i, i) + w)
    return ret

INF = 10**6
V, E = map(int, input().split())
A = [[INF]*V for _ in range(V)]
for _ in range(E):
    s, t, w = map(int, input().split())
    A[s][t] = w
ans = rec(0, 0)
print(ans if ans != INF else -1)

### FIXED CODE ###

def read_list(t): return [t(x) for x in input().split()]
def read_line(t): return t(input())
def read_lines(t, N): return [t(input()) for _ in range(N)]

INF = 1<<27
V, E = read_list(int)
edge = [[] for _ in range(V)]
for _ in range(E):
    fr, to, cost = map(int, input().split())
    edge[fr].append((to, cost))

dp = [[INF] * V for _ in range(1<<V)]
dp[(1 << V) - 1][0] = 0
for state in reversed(range((1<<V)-1)):
    for v in range(V):
        for to, cost in edge[v]:
            if not (state >> to & 1):
                dp[state][v] = min(dp[state][v], dp[state | 1 << to][to] + cost)
print(dp[0][0] if dp[0][0] != INF else -1)
### BUGGY CODE ###

SENTINEL = 2 ** 32
cnt = 0
def merge(A, left, mid, right):
    n1 = mid - left
    n2 = right - mid
    L = [i for i in range(n1 +1)]
    R = [i for i in range(n2 +1)]
    for i in range(n1):
        L[i] = A[left + i]
    for i in range(n2):
        R[i] = A[mid + i]
    L[n1] = SENTINEL
    R[n2] = SENTINEL
    i = 0
    j = 0
    for k in range(left, right):
        global cnt
        cnt += 1
        if L[i] <= R[j]:
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1

def merge_sort(A, left, right):
    if left+1 < right:
        mid = int((left + right)/2)
        merge_sort(A, left, mid)
        merge_sort(A, mid, right)
        merge(A, left, mid, right)

n = input()
A = list(map(int, input().split()))
merge_sort(A,0,len(A))
print(*A)
print(cnt)

### FIXED CODE ###

SENTINEL = 2 ** 32
cnt = 0
def merge(A, left, mid, right):
    L = A[left:mid] + [SENTINEL]
    R = A[mid:right] + [SENTINEL]
    
    i = 0
    j = 0
    for k in range(left, right):
        global cnt
        cnt += 1
        if L[i] <= R[j]:
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1

def merge_sort(A, left, right):
    if left + 1 < right:
        mid = (left + right) // 2
        merge_sort(A, left, mid)
        merge_sort(A, mid, right)
        merge(A, left, mid, right)

n = input()
A = list(map(int, input().split()))
merge_sort(A,0,len(A))
print(*A)
print(cnt)
### BUGGY CODE ###

import math

N=int(input())

a=math.ceil(math.sqrt(N))

for i in range(a,N+1):
  if N%i==0:
    r=N//i
    print(max(len(str(i)),len(str(r))))
    exit()

### FIXED CODE ###

import math
 
N=int(input())
 
a=math.floor(math.sqrt(N))
 
for i in range(a,0,-1):
  if N%i==0:
    r=N//i
    print(max(len(str(i)),len(str(r))))
    exit()

print(len(str(N)))
### BUGGY CODE ###

import collections
N, M, P = map(int, input().split())
e = collections.defaultdict(list)
for _ in range(M):
  u, v, c = map(int, input().split())
  e[u].append((v, c))
def isConnected(n):
  if n == N:
    return True
  vis = [0] * (N + 1)
  que = collections.deque([])
  que.append(n)
  while que:
    nc = que.popleft()
    vis[nc] = 1
    for o in e[nc]:
      if o[0] == N:
        return True
      if visited[o[0]] == 0:
        que.append(o[0])
  return False
inf = 10 ** 10
visited = [0] * (N + 1)
earn = [-inf] * (N + 1)
earn[1] = 0
Q = collections.deque([])
Q.append(1)
while Q:
  n = Q.popleft()
  visited[n] = 1
  for o in e[n]:
    if visited[o[0]] == 0:
      Q.append(o[0])
      earn[o[0]] = max(o[1] + earn[n] - P, earn[o[0]])
    else:
      if earn[o[0]] < o[1] + earn[n] - P:
        if isConnected(o[0]) == True:
          print(-1)
          exit(0)
  visited[n] = 0
print(max(earn[N], 0))

### FIXED CODE ###

import collections
import sys
import time
sys.setrecursionlimit(10 ** 5)
N, M, P = map(int, input().split())
e = collections.defaultdict(list)
st = time.time()
for _ in range(M):
  u, v, c = map(int, input().split())
  e[u].append((v, c))
def isConnected(n):
  if n == N:
    return True
  vis = [0] * (N + 1)
  que = collections.deque([])
  que.append(n)
  while que:
    nc = que.popleft()
    vis[nc] = 1
    for o in e[nc]:
      if o[0] == N:
        return True
      if vis[o[0]] == 0:
        que.append(o[0])
  return False
inf = 10 ** 10
visited = [0] * (N + 1)
earn = [-inf] * (N + 1)
earn[1] = 0
def dfs(now):
  global visited
  global earn
  nt = time.time() - st
  if nt > 1.95:
    print(max(earn[N], 0))
    exit(0)
  visited[now] = 1
  for n in e[now]:
    if visited[n[0]] == 0:
      if n[1] + earn[now] - P > earn[n[0]]:
        earn[n[0]] = n[1] + earn[now] - P
        dfs(n[0])
        visited[n[0]] = 0
    else:
      if earn[n[0]] < n[1] + earn[now] - P:
        if isConnected(n[0]) == True:
          print(-1)
          exit(0)
dfs(1)
print(max(earn[N], 0))
### BUGGY CODE ###

n, k = map(int, input().split(' '))
a = list(map(int, input().split(' ')))
score = 1
for i in range(k):
    score *= a[i]
for i in range(k-1, n-1):
    if int(score) < int(score*a[i+1]/a[i-k+1]):
        print('Yes')
    else:
        print('No')
    score = score*a[i+1]/a[i-k+1]

### FIXED CODE ###

n, k = map(int, input().split(' '))
a = list(map(int, input().split(' ')))
for i in range(k, n):
    score = 1
    if score < score*a[i]/a[i-k]:
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

s = input()
t = input()

ls = len(s)
lt = len(t)

dp = [[0 for _ in range(lt + 1)] for _ in range(ls + 1)]  # dp[ls][lt] = LCS_length

for i in range(ls):
    for j in range(lt):
        if s[i] == t[j]:
            dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j] + 1)
        dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i + 1][j])
        dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j + 1])

res = ''
i = ls
j = lt
while i > 0 and j > 0:
    if dp[i][j] == dp[i - 1][j]:
        i -= 1
    elif dp[i][j] == dp[i][j - 1]:
        j -= 1
    else:
        res = s[i - 1] + res
        i -= 1
        j -= 1
print(res)


### FIXED CODE ###

s = input()
t = input()

ls = len(s)
lt = len(t)

dp = [[0 for _ in range(lt + 1)] for _ in range(ls + 1)]  # dp[ls][lt] = LCS_length

for i in range(ls):
    for j in range(lt):
        if s[i] == t[j]:
            dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j] + 1)
        dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i + 1][j])
        dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j + 1])

res = ''
i = ls
j = lt
while i > 0 and j > 0:
    if dp[i][j] == dp[i - 1][j]:
        i -= 1
    elif dp[i][j] == dp[i][j - 1]:
        j -= 1
    else:
        res = s[i - 1] + res
        i -= 1
        j -= 1
print(res)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

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

for i in range(N, M+1):
    if M%i==0:
        print(M//i)
        break




### FIXED CODE ###

import sys
input = sys.stdin.readline

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

yakusu = []

for i in range(1,int(M**0.5)+1):
    if M%i==0:
        yakusu.append(i)
        if M//i!=i:
            yakusu.append(M//i)
    
yakusu.sort()
for i in yakusu:
    if i>=N:
        print(M//i)
        break
### BUGGY CODE ###

n = int(input())
li1 = list(map(int,input().split()))
m = int(input())
li2 = list(map(int,input().split()))
cnt = 0
 
for i in li2:
    if i in li1:
        cnt +=1
print(cnt)

### FIXED CODE ###

n = int(input())
S = set(map(int, input().split()))
q = int(input())
T = list(map(int, input().split()))

sum = 0

for i in T:
    if i in S:
        sum +=1
        
print(sum)
### BUGGY CODE ###


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

route = [0]
now_i = 0
loop_len = 0
for i in range(1, N):
    next_i = A[now_i]-1
    if next_i in route:
        loop_len = i - route.index(next_i)
        break
    route.append(next_i)
    now_i = next_i


base = len(route) - loop_len

if K < len(route):
    print(route[K]+1)
else:
    K -= base
    m = K % loop_len
    idx = route[base:][m]
    print(idx+1)



### FIXED CODE ###

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

route = [0]
routeset = {0}
now_i = 0
loop_len = 0
for i in range(1, N):
    next_i = A[now_i]-1
    if next_i in routeset:
        loop_len = i - route.index(next_i)
        break
    routeset.add(next_i)
    route.append(next_i)
    now_i = next_i


base = len(route) - loop_len

if K < len(route):
    print(route[K]+1)
else:
    K -= base
    m = K % loop_len
    idx = route[base:][m]
    print(idx+1)
### BUGGY CODE ###

from collections import *
H,W = map(int,input().split())
ch,cw = map(int,input().split())
dh,dw = map(int,input().split())
S = 2*[(W+4)*"#"]+["##"+input()+"##" for h in range(H)]+2*[(W+4)*"#"]
ans = [(W+4)*[-1] for h in range(H+4)]
ans[ch+1][cw+1] = 0
move = [[-1,0],[1,0],[0,-1],[0,1]]
magic = [[-2,-2],[-2,-1],[-2,0],[-2,1],[-2,2],[-1,-2],[-1,-1],[-1,1],[-1,2],[0,-2],[0,2],[1,-2],[1,-1],[1,1],[1,2],[2,-2],[2,-1],[2,0],[2,1],[2,2]]

for h in range(H+4):
  for w in range(W+4):
    if S[h][w]=="#":
      ans[h][w]=-2

P = deque([[ch+1,cw+1]])
Q = deque([])

while P:
  x,y = P.popleft()
  Q.append([x,y])
  for dx,dy in move:
    if ans[x+dx][y+dy]==-1:
      ans[x+dx][y+dy] = ans[x][y]
      P.append([x+dx,y+dy])
  
  if len(P)==0:
    while Q:
      x,y = Q.popleft()
      for dx,dy in magic:
        if ans[x+dx][y+dy]==-1:
          ans[x+dx][y+dy] = ans[x][y]+1
          P.append([x+dx,y+dy])

print(ans[dh+1][dw+1])

### FIXED CODE ###

from collections import *

def main():
    H,W = map(int, input().split())
    ch,cw = map(int, input().split())
    dh,dw = map(int, input().split())
    s = ["#"*(W+4)]
    s.append("#"*(W+4))
    for i in range(H):
        s.append("##"+input()+"##")
    s.append("#"*(W+4))
    s.append("#"*(W+4))
    
    ans = [[-1]*(W+4) for _ in range(H+4)]
    for i in range(H+4):
        for j in range(W+4):
            if s[i][j] == "#":
                ans[i][j] = -2
    ch += 1; cw += 1
    dh += 1; dw += 1
    ans[ch][cw] = 0
    
    move = [[-1,0],[1,0],[0,-1],[0,1]]
    magic = [
        [-2,-2],[-2,-1],[-2,0],[-2,1],[-2,2],\
        [-1,-2],[-1,-1],[-1,0],[-1,1],[-1,2],\
        [0,-2],[0,-1],[0,0],[0,1],[0,2],\
        [1,-2],[1,-1],[1,0],[1,1],[1,2],\
        [2,-2],[2,-1],[2,0],[2,1],[2,2]
        ]
    
    mylist = deque([[ch,cw]])
    mylist2 = deque([])
    while len(mylist) > 0:
        x,y = mylist.popleft()
        mylist2.append([x,y])
        for p,q in move:
            v1,v2 = x+p,y+q
            if ans[v1][v2] == -1:
                mylist.append([v1,v2])
                ans[v1][v2] = ans[x][y]
        if len(mylist) == 0:
            while len(mylist2) > 0:
                x2,y2 = mylist2.popleft()
                for v1,v2 in magic:
                    i,j = x2+v1,y2+v2
                    if ans[i][j] == -1:
                        ans[i][j] = ans[x2][y2]+1
                        mylist.append([i,j])
    print(ans[dh][dw])
 
if __name__ == "__main__":
    main()
### BUGGY CODE ###

from sys import stdin
n = int(input())
r=[int(input()) for i in range(n)]
rv = r[::-1][:-1]
m = None
for j,r_j in enumerate(rv):
    r_i = min(r[:-(j+1)])
    t = r_j - r_i
    if m == None or t > m:
        m = t
print(m)

### FIXED CODE ###

n = int(input())
minv = int(input())
maxv = -2*10**9
for i in range(n-1):
    r = int(input())
    maxv = max(maxv,r-minv)
    minv = min(minv,r)
print(maxv)
### BUGGY CODE ###

# 15
import sys


def input(): return sys.stdin.readline().strip()
def I(): return int(input())
def LI(): return list(map(int, input().split()))
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def S(): return input()
def LS(): return input().split()


INF = float('inf')


n = I()
d = LI()
m = I()
t = LI()
d.sort()
t.sort()
ans = 'YES'
i = 0
for elem in d:
    # print(elem, t[0])
    if t[0] == elem:
        t.pop(0)
    if len(t) == 0:
        break
if len(t) != 0:
    ans = 'NO'
print(ans)


### FIXED CODE ###

# 15
from collections import Counter
import sys


def input(): return sys.stdin.readline().strip()
def I(): return int(input())
def LI(): return list(map(int, input().split()))
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def S(): return input()
def LS(): return input().split()


INF = float('inf')


n = I()
d = LI()
m = I()
t = LI()
d.sort()
t.sort()
c_t = Counter(t)
c_d = Counter(d)
# print(c_t.items())
# print(c_d.items())
ans = 'YES'
i = 0
c_d = dict([(k, v) for k, v in c_d.items() if k in c_t.keys()])
if len(c_d) != len(c_t):
    ans = 'NO'
    print(ans)
    exit()
for (k_t, v_t), (k_d, v_d) in zip(c_t.items(), c_d.items()):
    if v_t > v_d:
        ans = 'NO'
        break
print(ans)