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

temparr = input()
from heapq import heappush, heappop
temparr = temparr.split()
n = int(temparr[0])
edg = int(temparr[1])
dicts = {}
secdict = {}
for e in range(edg):
    temparr = input()
    temparr = temparr.split()
    edgearr = []
    for i in temparr:
        edgearr.append(int(i))
    first = int(edgearr[0])
    sec = int(edgearr[1])
    if first not in dicts:
        dicts[first] = []
    dicts[first].append(sec)
    if sec not in secdict:
        secdict[sec] = 1 
head = []
for i in range(1, n + 1):
    if i not in secdict:
        heappush(head, (0, i))
maxdist = [0 for _ in range(n + 1)]
while head:
    cur = heappop(head)
    curdis = int(cur[0])
    node = cur[1]
    nextdis = maxdist[node] + 1
    if node not in dicts:
        continue 
    for neigh in dicts[node]:
        if maxdist[neigh] < nextdis:
            negdis = nextdis * -1
            maxdist[neigh] = nextdis
            heappush(head,(nextdis, neigh))

print(max(maxdist))
    

    
    
    
    
    
    

### FIXED CODE ###

temparr = input()
from heapq import heappush, heappop

import sys
x=150000
sys.setrecursionlimit(x)
temparr = temparr.split()
n = int(temparr[0])
edg = int(temparr[1])
dicts = {}
secdict = {}
firstdict = {}
for e in range(edg):
    temparr = input()
    temparr = temparr.split()
    edgearr = []
    for i in temparr:
        edgearr.append(int(i))
    first = int(edgearr[0])
    sec = int(edgearr[1])
    if first not in dicts:
        dicts[first] = []
    dicts[first].append(sec)
    if first not in firstdict:
        firstdict[first] = 1 
tail = []
ans = {}

for i in range(1, n + 1):
    if i not in firstdict:
        tail.append(i)
        ans[i] = 0
        
def dfs(node):
    global ans, dicts
    if node in ans:
        return ans[node]
    if node not in  dicts:
        return 0  
    best = 0 
    for neigh in dicts[node]:
        curnew = dfs(neigh) + 1
        if curnew > best:
            best = curnew
    ans[node] = best 
    return best
ans2 = 0 
for i in range(1, n + 1):
    ans2 = max(dfs(i), ans2)
print(ans2)
### BUGGY CODE ###

mod = 1000000007
n, m = map(int, input().split())
dat_m = []
dp = []
for i in range(m):
    dat_m.append(int(input()))
dp.append(1)
for i in range(1, n + 1):
    t = 0
    t = dp[i - 1]
    if i > 1:
        t += dp[i - 2]
    if i in dat_m:
        t = 0
    t = t % mod
    dp.append(t)

print(dp[n])

### FIXED CODE ###

mod = 1000000007
n, m = map(int, input().split())
dat_m = []
dp = [0] * (n + 1)
for i in range(m):
    t = int(input())
    dp[t] = -1

dp[0] = 1
for i in range(1, n + 1):
    if dp[i] == -1:
        dp[i] = 0
        continue
    dp[i] = dp[i - 1]
    if i > 1:
        dp[i] += dp[i - 2]
    if i in dat_m:
        dp[i] = 0
    dp[i] = dp[i] % mod

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

import numpy as np
N, K = map(int,input().split())
H = np.array([int(input()) for _ in range(0, N)])
H = np.sort(H)
#print(H)
H_diff = abs(H[1:]-H[:-1])
#print(H_diff)
best = np.sum(H_diff[0:K-1])
for i in range(0, len(H_diff)-K+2):
    #print(i)
    if np.sum(H_diff[i:i+K-1]) < best:
        #print(H_diff[i:i+K-1])
        best = np.sum(H_diff[i:i+K-1])
#print('best:{}'.format(best))
print(best)

### FIXED CODE ###

import numpy as np
N, K = map(int,input().split())
H = np.array([int(input()) for _ in range(0, N)])
H = np.sort(H)
H_diff = np.diff(H)
best = int(np.min(np.convolve((H_diff), np.ones(K-1), mode='valid')))
print(best)
### BUGGY CODE ###

from collections import Counter
n=int(input())
l=[]
for i in range(n):
    s=input()
    l.append(Counter(s))
ans=0

for i in range(n):
    for j in range(i+1,n):
         if l[i]==l[j]:
             ans+=1
print(ans)

### FIXED CODE ###

from collections import Counter
n=int(input())
l={}
ans=0
for i in range(n):
  s=input()
  ss=sorted(s)
  s="".join(ss)
  ans+=l.setdefault(s, 0) 
  l[s]+=1
print(ans)
### BUGGY CODE ###

N = int(input())
import sys
sys.setrecursionlimit(1000000000)
MOD = 10**9+7
E = {}
for i in range(0,N+1):
    E[i] = []
for i in range(N-1):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    E[a].append(b)
    E[b].append(a)

dp = [ [0 for i in range(2)] for j in range(100100)]

def dfs(c,p):
    dp[c][0],dp[c][1] = 1,1
    for to in E[c]:
        if to != p:
            dfs(to,c)
            dp[c][0] *= dp[to][0] + dp[to][1]
            dp[c][1] *= dp[to][0]


dfs(0,-1)

ans = (dp[0][0] + dp[0][1]) % MOD
print(ans)


### FIXED CODE ###

from heapq import heappush, heappop
import collections
import math
import heapq
from collections import defaultdict
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
MOD = 10 ** 9 + 7
inf = float("inf")


def main():
    N = int(input())
    E = {}
    for i in range(0, N+1):
        E[i] = []
    for i in range(N-1):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        E[a].append(b)
        E[b].append(a)

    dp = [[0 for i in range(2)] for j in range(100100)]

    def dfs(c, p):
        dp[c][0], dp[c][1] = 1, 1
        for to in E[c]:
            if to != p:
                dfs(to, c)
                dp[c][0] *= dp[to][0] + dp[to][1]
                dp[c][1] *= dp[to][0]

    dfs(0, -1)

    ans = (dp[0][0] + dp[0][1]) % MOD
    print(ans)


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

N = int(input())
S = input()

ans = 0
for i in range(len(S)):    
    for j in range(i, len(S)):    
        for k in range(j, len(S)):
            if(S[i] != S[j] and S[j] != S[k] and S[k] != S[i]):
                if (j - i != k - j):
                    ans+=1
print(ans)
    

### FIXED CODE ###

N = int(input())
S = input()

R = []
G = []
B = []
ans = 0
for i in range(len(S)):
    if S[i] == "R":
        R.append(i)
    if S[i] == "G":
        G.append(i)
    if S[i] == "B":
        B.append(i)
rem = 0
setB = set(B)

for r in R:
    for g in G:
        if g - abs(r - g) in setB:
            rem += 1
        if r - abs(g - r) in setB:
            rem += 1
        if (g + r) / 2 in setB:
            rem += 1
        if g + abs(r - g) in setB:
            rem += 1
        if r + abs(g - r) in setB:
            rem += 1


print(len(R)*len(G)*len(B) - rem)
### BUGGY CODE ###

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

n=0
for i in range(0,N):
  if A[i]<0:
    n=n+1
    AA=A.pop(i)
    A.insert(i,(-1)*AA)

if n%2==0:
  print(sum(A))
else:
  print(sum(A)-2*min(A))

### FIXED CODE ###

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

n=0
sm=0
if A[0]>0:
  mn=A[0]
else:
  mn=(-1)*A[0]


for i in range(0,N):
  if A[i]<0:
    n=n+1
    sm=sm-A[i]
    if (-1)*A[i]<mn:
      mn=(-1)*A[i]
  else:
    sm=sm+A[i]
    if A[i]<mn:
      mn=A[i]
if n%2==0:
  print(sm)
else:
  print(sm-2*mn)
### BUGGY CODE ###

N = int(input())

A = list(map(int, input().split()))
sum = 0
for i in range(N-1):
    for m in range(i+1, N):
        sum += A[i]*A[m]

print(int(sum%(1e9 + 7)))

### FIXED CODE ###

N = int(input())

A = list(map(int, input().split()))
S = sum(A)
ans = 0
for i in range(N):
    S -= A[i]
    ans += A[i] * S
    

ans = ans % (10 ** 9  +7)        

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

s = list(input())
q = int(input())
forward = True
for _ in range(q):
    que = list(input().split())
    if int(que[0]) == 1:
        if forward:
            forward = False
        else:
            forward = True
    else:
        if (int(que[1]) == 1 and forward) or (int(que[1]) == 2 and not forward):
            s = [que[2]] + s
        else:
            s .append(que[2])
if forward:
    print("".join(s))
else:
    print("".join(reversed(s)))

### FIXED CODE ###

from collections import deque
s = input()
q = int(input())
f = ""
b = ""
forward = True
for _ in range(q):
    que = list(input().split())
    if int(que[0]) == 1:
        if forward:
            forward = False
        else:
            forward = True
    else:
        if (int(que[1]) == 1 and forward) or (int(que[1]) == 2 and not forward):
            f+=que[2]
        else:
            b+=que[2]

if forward:
    print(f[::-1]+s+b)
else:

    print(b[::-1]+s[::-1]+f)
### BUGGY CODE ###

import math

def permutations_count(n, r):
    if (n < 2):
        return 0
    else:
        return math.factorial(n) // math.factorial(n - r)

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

bar = {}

for i in range(N):
    if (A[i] in bar):
        bar[A[i]] = bar[A[i]] + 1
    else:
        bar[A[i]] = 1

partOfNum = {}
lackPartOfNum = {}

for j in bar.keys():
    tmp = permutations_count(bar[j], 2)
    partOfNum[j] = int(tmp / 2)
    tmp = permutations_count(bar[j] - 1, 2)
    lackPartOfNum[j] = int(tmp / 2)

allSum = 0
for l in partOfNum.keys():
    allSum += partOfNum[l]

for i in range(N):
    print(allSum - partOfNum[A[i]] + lackPartOfNum[A[i]])


### FIXED CODE ###

import math

def permutations_count(n, r):
    if (n < 2):
        return 0
    else:
        return math.factorial(n) // math.factorial(n - r)

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

bar = {}

for i in range(N):
    if (A[i] in bar):
        bar[A[i]] = bar[A[i]] + 1
    else:
        bar[A[i]] = 1

partOfNum = {}
lackPartOfNum = {}

for j in bar.keys():
    tmp = permutations_count(bar[j], 2)
    partOfNum[j] = int(tmp / 2)
#   tmp = permutations_count(bar[j] - 1, 2)
    lackPartOfNum[j] = partOfNum[j] - (bar[j] - 1)

allSum = 0
for l in partOfNum.keys():
    allSum += partOfNum[l]

for i in range(N):
    print(allSum - partOfNum[A[i]] + lackPartOfNum[A[i]])
### BUGGY CODE ###

#!/usr/bin/env python3
def main():
    import numpy as np

    N, K = map(int, input().split())
    S = set()
    for _ in range(K):
        l, r = map(int, input().split())
        for n in range(l, r + 1):
            S.add(n)
    MOD = 998244353

    dp = [0] * N
    dp[0] = 1
    dp = np.zeros(N, dtype=np.int64)
    dp[0] = 1
    for i in range(N):
        for d in S:
            if i >= d:
                dp[i] += dp[i - d] % MOD
    print(dp[-1] % MOD)


if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
def main():
    import numpy as np

    N, K = map(int, input().split())
    section = [list(map(int, input().split())) for _ in range(K)]
    MOD = 998244353

    dp = np.zeros(N + 1, dtype=np.int64)
    dp[1] = 1
    cumsum = np.zeros(N + 1, dtype=np.int64)
    cumsum[1] = 1
    for i in range(2, N + 1):
        for left_section, right_section in section:
            left = max(i - right_section - 1, 0)
            right = i - left_section
            if right < 0:
                continue
            dp[i] += cumsum[right] - cumsum[left]
        cumsum[i] = cumsum[i - 1] + dp[i]
        dp[i] %= MOD
        cumsum[i] %= MOD
    print(dp[N] % MOD)
    # print(dp)
    # print(cumsum)


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

# D
prime_num = set([2])
size = int(1e5)*2+1
for i in range(3,size,2):
    for p in prime_num:
        if i%p==0: break
        else: continue
    else:
        prime_num.add(i)

cnt = [0]*(int(1e5)+2)
for p in prime_num:
    if p<=int(1e5) and (p+1)//2 in prime_num:
        cnt[p] = 1
for i in range(1, int(1e5)+2):
    cnt[i] += cnt[i-1]
    
Q = int(input())
for _ in range(Q):
    l,r = map(int, input().split())
    print(cnt[r]-cnt[l])

### FIXED CODE ###

# D
N = 10**5
primes = set([])
is_prime = [True]*(N+1)
is_prime[0] = False
is_prime[1] = False
for i in range(2, N+1):
    if is_prime[i]:
        primes.add(i)
        for j in range(2, N//i+1):
            is_prime[j*i] = False
    
# like-2017
cnt = [0]*(int(1e5)+2)
for p in primes:
    if (p+1)//2 in primes:
        cnt[p] = 1
for i in range(1, int(1e5)+2):
    cnt[i] += cnt[i-1]
#print(cnt[:100])
    
Q = int(input())
for _ in range(Q):
    l,r = map(int, input().split())
    print(cnt[r]-cnt[l-1])
### BUGGY CODE ###

N=int(input())
word=set()
number=[]
S=list(map(int,input()))
for i in range(10):
    for j in range(10):
        for k in range(10):
           number.append([str(i)+str(j)+str(k)])
ans=0
for i in number:
    i,j,k=i[0][0],i[0][1],i[0][2]
    p1,p2,p3=-1,-1,-1
    for s in range(N):
        if S[s]==int(i) and p1==-1:
            p1=s
        elif S[s]==int(j) and p2<p1:
            p2=s
        elif S[s]==int(k) and p3<p2:
            p3=s
    if p1!=-1 and p2!=-1 and p3!=-1:
        if p1<p2<p3:
            # print(i, j, k)
            ans+=1

print(ans)




### FIXED CODE ###

def main():
  N = int(input())
  S = list(map(int,input()))
  ans = 0
  for i in range(10):
    for j in range(10):
      for k in range(10):
        flg = False
        flg2 = False
        for x in range(N):
          if flg2:
            break
          if not flg:
            if S[x] == i:
              flg = True
          else:
            if S[x] == j:
              flg2 = True
              if k in S[x+1:]:
                ans +=1
  print(ans)
main()
### BUGGY CODE ###

K=int(input())
answer=0
count=0
i=1

while count<K:
    if i<=9:
        count+=1
        if count==K:
            answer=i
            break
    else:
        S=str(i)
        judge=True
        for j in range(1,len(S)):
            if abs(int(S[j-1])-int(S[j]))<=1:
                pass
            else:
                judge=False
        if judge==True:
            count+=1
            if count==K:
                answer=i
                break
    i+=1
print(answer)

### FIXED CODE ###

from queue import Queue 
K=int(input())

q=Queue()

for i in range(1,min(9,K)+1):
    q.put(i)

for k in range(K):
    a=q.get()
    #print(a)
    if k!=K-1:
        b=a%10
        for j in range(max(0,b-1),min(9,b+1)+1):
            q.put(int(str(a)+str(j)))
    else:
        print(a)
### BUGGY CODE ###

#入力
N, Y = map(int, input().split())


#総当たりで合計金額を算出
x = []
y = []
z = []

for num_ten_thousand in range(0, N+1):
    for num_five_thousand in range(0, N+1):
        for num_one_thousand in range(0, N+1):
            
            #合計金額を算出
            total = num_ten_thousand*10000 + num_five_thousand*5000 + num_one_thousand*1000
            
            #（合計金額がYと等しいか・合計枚数がNと等しいか）を確認し答えをリストに格納
            if Y==total and N==num_ten_thousand+num_five_thousand+num_one_thousand:
                x.append(num_ten_thousand)
                y.append(num_five_thousand)
                z.append(num_one_thousand)
                
                
#答えを出力
if not x:
    print(-1, -1, -1, sep=" ")
    
else:
    print(x[0], y[0], z[0], sep=" ")

### FIXED CODE ###

#入力
N, Y = map(int, input().split())


#総当たりで合計金額を算出
x = []
y = []
z = []

for num_ten_thousand in range(0, N+1):
    for num_five_thousand in range(0, N+1):
            
            #千円の枚数を算出
            if N-(num_ten_thousand+num_five_thousand)>=0:
                num_one_thousand = N-(num_ten_thousand+num_five_thousand)
            
            #合計金額を算出
            total = num_ten_thousand*10000 + num_five_thousand*5000 + num_one_thousand*1000
            
            #（合計金額がYと等しいか・合計枚数がNと等しいか）を確認し答えをリストに格納
            if Y==total and N==num_ten_thousand+num_five_thousand+num_one_thousand:
                x.append(num_ten_thousand)
                y.append(num_five_thousand)
                z.append(num_one_thousand)
                
                
#答えを出力
if not x:
    print(-1, -1, -1, sep=" ")
    
else:
    print(x[0], y[0], z[0], sep=" ")
### BUGGY CODE ###

n = int(input())
s = input()

ans = 0
for i in range(1000):
    p = str(i).zfill(3)
    p_index = 0
    for j in range(n):
        if p[p_index] == s[j]:
            p_index += 1
            if p_index == 3:
                break
    if p_index == 3:
        ans += 1

print(ans)


### FIXED CODE ###

n = int(input())
s = input()

ans = 0
# 000 ～　999 がsから作成できるか確認していく
for i in range(1000):
    p = str(i).zfill(3)

    s_index_100 = s.find(p[2])
    if s_index_100 == -1:
        continue

    s_index_10 = s.find(p[1], s_index_100+1)
    if s_index_10 == -1:
        continue

    s_index_1 = s.find(p[0], s_index_10+1)
    if s_index_1 == -1:
        continue
    ans += 1

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

import sys
from collections import defaultdict
def input():
	return sys.stdin.readline()[:-1]

MOD = 1e9+7
n, x = map(int, input().split())
s = list(map(int, input().split()))
s.sort(reverse=True)
dp = defaultdict(int)
dp[x] = 1
for i in range(n):
	dpp = defaultdict(int)
	for j in range(x+1):
		dpp[j] += (n-1-i) * dp[j]
		dpp[j%s[i]] += dp[j]
	for j in range(x+1):
		dpp[j] %= MOD
	dp = dpp
#print(dp)
ans = 0
for j in range(x+1):
	ans += dp[j] * j
	ans %= MOD
print(int(ans))

### FIXED CODE ###

import sys
from collections import defaultdict
def input():
	return sys.stdin.readline()[:-1]

MOD = 1e9+7
n, x = map(int, input().split())
s = list(map(int, input().split()))
s.sort(reverse=True)
dp = defaultdict(int)
dp[x] = 1
for i in range(n):
	ss = s[i]
	dpp = defaultdict(int)
	for key, value in dp.items():
		dpp[key] += (n-1-i) * value
		dpp[key%ss] += value
	for key in dpp.keys():
		dpp[key] %= MOD
	dp = dpp
ans = 0
for key, value in dp.items():
	ans += value * key
	ans %= MOD
print(int(ans))
### BUGGY CODE ###

n = int(input())
s = []
ctr = 0

for _ in range(n):
    si = input()
    slist = sorted(list(si))
    for i in range(len(s)):
        if slist == s[i]:
            ctr += 1
    s.append(slist)

print(ctr)

### FIXED CODE ###

n = int(input())
num_of_anagram = dict()
ans = 0

for _ in range(n):
    s = input()
    s = ''.join(sorted(list(s)))
    if s in num_of_anagram:
        num_of_anagram[s] += 1
        ans += num_of_anagram[s]
    else:
        num_of_anagram[s] = 0

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

n,k,q=map(int,input().split())
a=[k]*n
for i in range(q):
  o=int(input())
  a[o-1]+=1
  for j in range(n):
    a[j]-=1

for s in range(n):
  if a[s]>0:
    print("Yes")
  else:
    print("No")


### FIXED CODE ###

n,k,q=map(int,input().split())
a=[k-q]*n
for i in range(q):
  o=int(input())
  a[o-1]+=1
  

for s in range(n):
  if a[s]>0:
    print("Yes")
  else:
    print("No")
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
amin = min(a)
amax = max(a)
ans = 0
for x in range(amin,amax+1):
	    p = 0
	    p += a.count(x)
	    p += a.count(x+2)
	    p += a.count(x+1)
	    ans = max(ans,p)
print(ans)


### FIXED CODE ###

import collections
n = int(input())
a = list(map(int,input().split()))
c = dict(collections.Counter(a))
c = dict(sorted(c.items(),key = lambda x:x[0]))

ans = 0
for i in range(1,10**5):
  cnt = 0
  try:
    cnt += c[i-1]
  except KeyError:
    pass
  
  try:
    cnt += c[i]
  except KeyError:
    pass
    
  try:
    cnt += c[i+1]
  except KeyError:
    pass
    
  ans = max(ans,cnt)  
  
print(ans)
### BUGGY CODE ###

N = int(input())
A_list = list(input().split())

answer = 1
for a in A_list:
    answer *= int(a)

if len(str(answer-1))>18:
    print(-1)
else:
    print(answer)


### FIXED CODE ###

N = int(input())
A_list = list(map(int,input().split()))
A_list.sort()
#print(A_list)
if A_list[0]==0:
    answer = 0
else:      
    answer = 1
    for a in A_list:
        answer *= a
        if len(str(answer-1)) > 18:
            answer = -1
            break
print(answer)
### BUGGY CODE ###

from collections import defaultdict
 
class Solution:
    def main(self):
        N = int(input())
        A = []
        for i in range(N):
            a = list(map(lambda x: int(x)-1, input().split())) + [-1]
            A.append(a)
 
        hashmap = defaultdict(set)
        for i in range(N):
            hashmap[A[i][0]].add(i)
 
        # print(hashmap)
 
        cnt = 0
        old_cnt = 0
        for day in range(1, N*(N-1)+1):
            cands = set()
            for i in range(N):
                if i in hashmap and A[i][0] in hashmap[i]:
                    if i < A[i][0]:
                        cands.add((i, A[i][0]))
                    else:
                        cands.add((A[i][0], i))
 
            for x, y in cands:
                # print(x, y)
                hashmap[y].remove(x)
                hashmap[x].remove(y)
                hashmap[A[x][1]].add(x)
                hashmap[A[y][1]].add(y)
                A[x].pop(0)
                A[y].pop(0)
                cnt += 1
 
            if cnt == N*(N-1)//2:
                print(day)
                break
            elif cnt == old_cnt:
                print(-1)
                break
            else:
                old_cnt = cnt
                
if __name__ == '__main__':
    Solution().main()

### FIXED CODE ###

from collections import defaultdict

class Solution:
    def main(self):
        N = int(input())
        A = []
        for i in range(N):
            a = list(map(lambda x: int(x)-1, input().split())) + [-1]
            A.append(a)

        hashmap = defaultdict(set)
        for i in range(N):
            hashmap[A[i][0]].add(i)

        # print(hashmap)

        cnt = 0
        old_cnt = 0
        checklist = set(range(N))

        for day in range(1, N*(N-1)+1):
            cands = set()
            for i in checklist:
                if i in hashmap and A[i][0] in hashmap[i]:
                    if i < A[i][0]:
                        cands.add((i, A[i][0]))
                    else:
                        cands.add((A[i][0], i))

            for x, y in cands:
                # print(x, y)
                hashmap[y].remove(x)
                hashmap[x].remove(y)
                hashmap[A[x][1]].add(x)
                hashmap[A[y][1]].add(y)
                A[x].pop(0)
                A[y].pop(0)
                cnt += 1

            if cnt == N*(N-1)//2:
                print(day)
                break
            elif cnt == old_cnt:
                print(-1)
                break
            else:
                old_cnt = cnt
                checklist = set().union(*cands)
                # print(cands)
                # print(checklist)


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

K = int(input())

queue = [1, 2, 3, 4, 5, 6, 7, 8, 9]

c = 0
while c < K: 
    x = queue.pop(0)
    if x % 10 != 0:  
        queue.append(10 * x + x % 10 - 1)
    queue.append(10 * x + x % 10) 
    if x % 10 != 9:
        queue.append(10 * x + x % 10 + 1)
    c += 1

print(x)

### FIXED CODE ###

from collections import deque
K = int(input())

q = deque([1, 2, 3, 4, 5, 6, 7, 8, 9])

for _ in range(K):
    x = q.popleft()
    xmod = x % 10
    if xmod != 0:
        q.append(10 * x + xmod - 1)
    q.append(10 * x + xmod)
    if xmod != 9:
        q.append(10 * x + xmod + 1)
print(x)
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
ans=''
for i in range(n):
    ans+=str(a.index(i+1)+1)+' '
print(ans)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
b=list(range(1,n+1))
dic=dict(zip(a,b))
dic=sorted(dic.items())
c=[]
for i in dic:
    c.append(i[1])
print(*c)
### BUGGY CODE ###

N = int(input())
A = [int(i) for i in input().split()]
AS = sorted(A)

def f(x):
    B = [((x<=a)<<1)-1 for a in A]
    C = [N]
    [C.append(C[-1]+b) for b in B]

    r = 0
    Bit = [0] * (2*N+1)

    for i,c in enumerate(C):
        t=c-1
        while(t>0):
            r += Bit[t]
            t -= t&-t
        t=c-1
        while(t<=2*N+1):
            Bit[t] += 1
            t += t&-t
    return(r>=N*(N+1)//4)

l = 0
r = N-1
while l != r:
    if f(AS[(l+r+1)//2]):
        l = (l+r+1)//2
    else:
        r = (((l+r+1)//2)-1)
print(AS[r])


### FIXED CODE ###

N = int(input())
A = [int(i) for i in input().split()]
AS = sorted(list(set(A)))

def f(x):
    B = [((x<=a)<<1)-1 for a in A]
    C = [N]
    [C.append(C[-1]+b) for b in B]

    r = 0
    Bit = [0] * (2*N+1)

    for i,c in enumerate(C):
        t=c-1
        while(t>0):
            r += Bit[t]
            t -= t&-t
        t=c-1
        while(t<=2*N+1):
            Bit[t] += 1
            t += t&-t
    return(r>=N*(N+1)//4)

l = 0
r = len(AS)-1
while l != r:
    if f(AS[(l+r+1)//2]):
        l = (l+r+1)//2
    else:
        r = (((l+r+1)//2)-1)
print(AS[r])