Harryxun/stf_run huggingface dataset:
from collections import defaultdict

vertice,edge = map(int,input().split(" "))
cost = [[0 if m == n else float("inf") for n in range(vertice)] for m in range(vertice)]
link = defaultdict(dict)
weight = defaultdict(dict)

for e in range(edge):
    i,j,w = map(int,input().split(""))
    link[i] = link.get(i,set()) | {j}
    weight[i].update({j:w})

vertice_cnt = 0
while 1:
    if vertice_cnt >= vertice:
        print("NEGATIVE CYCLE")
        break
    update = False
    for source in range(vertice):
        for k,value in link.items():
            for v in value:
                if cost[source][v] > cost[source][k] + weight[k][v]:
                    cost[source][v] = cost[source][k] + weight[k][v]
                    update = True
    if not update:
        for o in range(vertice):

            print(*([n if n != float("INF") else "INF" for n in cost[o]]))
        break
    vertice_cnt += 1

### FIXED CODE ###

vertices, edges = (int(n) for n in input().split(" "))
cost_dp = [[float("inf") if n != m else 0 for n in range(vertices)] for m in range(vertices)]
for e in range(edges):
    v1, v2, weight = (int(n) for n in input().split(" "))
    cost_dp[v1][v2] = weight
for neg in range(2):
    updated = 0
    for t in range(vertices):
        for i in range(vertices):
            for k in range(vertices):
                if cost_dp[i][k] > cost_dp[i][t] + cost_dp[t][k]:
                    updated = 1
                    cost_dp[i][k] = cost_dp[i][t] + cost_dp[t][k]
if neg == 1 and updated:
    print("NEGATIVE CYCLE")
else:
    for ve in range(vertices):
        ans = ["INF" if n == float("inf") else n for n in cost_dp[ve]]
        print(*ans)
A,B = list(map()int, input().split())
if(A+B>=10):
  print("error")
else:
  print(A+B)

### FIXED CODE ###

A,B = list(map(int, input().split()))
if(A+B>=10):
  print("error")
else:
  print(A+B)
s = input()
ans = []

for i in range(len(s)):
    if s[i] == '0':
        ans.append('0')
    if s[i] == '1':
        ans.append('1')
    if s[i] == 'B':
        ans.pop(-1)

print(''.join(ans))


### FIXED CODE ###

s = input()
ans = []

for i in range(len(s)):
    if s[i] == '0':
        ans.append('0')
    if s[i] == '1':
        ans.append('1')
    if s[i] == 'B':
        if len(ans) != 0:
            ans.pop(-1)

print(''.join(ans))
n=int(input())
arr=list(map(int,input().split()))
if n < 2:
  print(0)
vis={}
vis[0] = 0
vis[1] = 0
if n > 1:
  vis[2] = abs(arr[0]-arr[1])
if n == 2:
  print(vis[2])
for i in range(3, n):
    step_1 = abs(arr[i-1]-arr[i-2]) + vis[i-1]
    step_2 = abs(arr[i-1]-arr[i-3]) + vis[i-2]
    vis[i] = min(step_1, step_2)
   
print(vis[i])

### FIXED CODE ###

n=int(input())
arr=list(map(int,input().split()))
if n < 2:
  print(0)
vis = [0] * n
vis[0] = 0
vis[1] = abs(arr[0]-arr[1])
for i in range(2, n):
    step_1 = abs(arr[i]-arr[i-1]) + vis[i-1]
    step_2 = abs(arr[i]-arr[i-2]) + vis[i-2]
    vis[i] = min(step_1, step_2)
print(vis[-1])
import math
S = input()
Q = int(input())

def reverse_list(S):
    S = ("")
    S.reverse()
    return ''.join(S)

def moji_tuika(S, f, c):
    if f == 1:
        return c + S
    else:
        return S + c

q = []
for i in range(Q):
    temp = input().split()
    if len(temp) == 1:
        q.append(1)
    else:
        q.append(temp)

for i in q:
    if type(i) == int:
        S = reverse_list(S)
    elif i[0] == 2:
        S = moji_tuika(S,int(i[1]),i[2])

print(S)


### FIXED CODE ###

from collections import deque

S = input()
Q = int(input())

lr = 'left'

def reverse_list(lr):
    if lr == 'right':
        return 'left'
    else:
        return 'right'

def moji_tuika(S, f, c, lr):
    if f == 1 and lr == 'left':
        S.appendleft(c)
    elif f == 1 and lr == 'right':
        S.append(c)
    elif f == 2 and lr == 'left':
        S.append(c)
    else:
        S.appendleft(c)
    return S

q = []
for i in range(Q):
    temp = input().split()
    if len(temp) == 1:
        q.append(1)
    else:
        q.append(temp)

S = deque(list(S))
for i in q:

    if type(i) == int:
        lr = reverse_list(lr)
    elif int(i[0]) == 2:
        S = moji_tuika(S,int(i[1]),i[2],lr)
if lr == 'right':
    S.reverse()

S = ''.join(S)
print(S)
import math
while True:
    try:
        l = map(int, raw_input().split())
        l1 = [int(i) for i in l]
        sum = (l1[0] + l1[1])
        print(int(math.log10(sum) + 1))
    except EOFError:
        break

### FIXED CODE ###

while True:
    try:
        a,b = map(int, input().split())
        print(len(str(a+b)))
    except EOFError:
        break
X = list(input())
con = X[len(X)-2:len(X)]
kak = X[0:len(X)-2]
kak = int("".join(kak))
con = int("".join(con))
if con>=5:
    imp1 = con//5
    imp2 = con%5
else:
    imp1 = 1
    imp2 = 0
#print(kak, imp1, imp2)
if kak>=imp1+imp2:
    print(1)
else:
    print(0)

### FIXED CODE ###

X = list(input())
if len(X)<=2:
    print(0)
    exit()
con = X[len(X)-2:len(X)]
kak = X[0:len(X)-2]
kak = int("".join(kak))
con = int("".join(con))
if con>=5:
    imp1 = con//5
    imp2 = con%5
else:
    imp1 = 1
    imp2 = 0
#print(kak, imp1, imp2)
if kak>=imp1+imp2:
    print(1)
else:
    print(0)
X, Y, Z, K = map(int, input().split())
A = sorted(list(map(int, input().split())), reverse=True)
B = sorted(list(map(int, input().split())), reverse=True)
C = sorted(list(map(int, input().split())), reverse=True)
#A~Cは降順でソート済み
lenA = X
lenB = Y
lenC = Z #分かりにくいので名前を変えただけ

#差分の配列を作る
difA = []
difB = []
difC = []
for i, a in enumerate(A):
  if i == 0:
    preA = a
    continue #0ならpreAに入れるだけ
  difA.append(preA - a)
  preA = a
for i, b in enumerate(B):
  if i == 0:
    preB = b
    continue #0ならpreBに入れるだけ
  difB.append(preB - b)
  preB = b
for i, c in enumerate(C):
  if i == 0:
    preC = c
    continue #0ならpreCに入れるだけ
  difC.append(preC - c)
  preC = c
#print(difA,difB,difC) #デバッグ用

cntA, cntB, cntC = sum(difA), sum(difB), sum(difC)
cntA, cntB, cntC = (1500*cntA)//(cntA+cntB+cntC),(1500*cntB)//(cntA+cntB+cntC),(1500*cntC)//(cntA+cntB+cntC)

setc = []
for i in range(0, min(cntA,lenA)):
  for j in range(0, min(cntB,lenB)):
    for k in range(0, min(cntC,lenC)):
      setc.append(A[i]+B[j]+C[k])
slist = sorted(setc,reverse=True)

for i in range(K):
  print(slist[i])

### FIXED CODE ###

X, Y, Z, K = map(int, input().split())
A = sorted(list(map(int, input().split())), reverse=True)
B = sorted(list(map(int, input().split())), reverse=True)
C = sorted(list(map(int, input().split())), reverse=True)
#A~Cは降順でソート済み
lenA = X
lenB = Y
lenC = Z #分かりにくいので名前を変えただけ

AB = []

for i in range(0, min(K,lenA)):
  for j in range(0, min(K,lenB)):
      AB.append(A[i]+B[j])
AB.sort(reverse=True)

ABC = []

for j in range(0, min(K,len(AB))):
  for k in range(0, min(K,lenC)):
      ABC.append(AB[j]+C[k])
ABC.sort(reverse=True)

for i in range(K):
  print(ABC[i])
A,B,C=map(int,input().split())
K=int(input())

m=max(A,B,C)
print((2**K)*m + (A+B+C-m)

### FIXED CODE ###

A,B,C=map(int,input().split())
K=int(input())

m=max(A,B,C)
print((2**K)*m + (A+B+C-m))
a, b, c, d = map(int, input().split(" "))
i = 0
while a > 0 or c > 0:
  if i%2 == 0:
    c -= b
    else:
      a -= d
  i += 1
print("YNeos"[i%2::2])

### FIXED CODE ###

import sys
from math import sqrt, gcd, ceil, log
from bisect import bisect
from collections import defaultdict
inp = sys.stdin.readline
read = lambda: list(map(int, inp().strip().split()))

# sys.setrecursionlimit(10**6)



def solve():
	a, b, c, d = map(int, input().split(" "))
	i = 0
	while a > 0 or c > 0:
		if i%2 == 0:
			c -= b
		else:
			a -= d
		i += 1
	print("YNeos"[i%2::2])



if __name__ == "__main__":
	solve()
import sys
sys.setrecursionlimit(10**6) 

h, w = map(int, input().split())
a = [input() for _ in range(h)]
mod = 10**9+7

dp = [[0 for _ in range(h+1)] for _ in range(w+1)]
dp[0][0] = 1

for i in range(h):
    for j in range(w):
        if (i+1 < h) and (a[i+1][j] == '.'):
            dp[i+1][j] += dp[i][j]
            dp[i+1][j] %= mod
        if (j+1 < w) and (a[i][j+1] == '.'):
            dp[i][j+1] += dp[i][j]
            dp[i][j+1] %= mod

print(dp[h-1][w-1])

### FIXED CODE ###

h, w = map(int, input().split())
a = [input() for _ in range(h)]
mod = 10**9+7

dp = [[0 for _ in range(w+1)] for _ in range(h+1)]
dp[0][0] = 1

for i in range(h):
    for j in range(w):
        if i+1 < h and a[i+1][j] == '.':
            dp[i+1][j] += dp[i][j]
            dp[i+1][j] %= mod
        if j+1 < w and a[i][j+1] == '.':
            dp[i][j+1] += dp[i][j]
            dp[i][j+1] %= mod

print(dp[h-1][w-1])
N, K = input().split()

dislike = set(list(map(int, input().split())))


next_map = {}
for i in range(10):
    for j in range(i,10):
        if j not in dislike:
            if i == 0:
                min_digit = j
            next_map.update({ i : j })
            break
        next_map.update({ i : min_digit })
max_digit = max(next_map.values())

num = len(list(N))

count = num
cand = []
for n in list(N):
    n = int(n)
    if n in dislike:
        n_ = next_map[n]
        cand.append(n_)
        count -= 1
        cand.extend(count*[min_digit])
        break
    else:
        cand.append(n)
cand = int("".join(list(map(str, cand))))
if int(N) <= cand:
    print(cand)
else:
    if min_digit == 0:
        next_min = next_map[1]
        cand = [next_min] + num * [0]
    else:
        cand = (num + 1) * [min_digit]
    cand = int("".join(list(map(str, cand))))
    print(cand)

### FIXED CODE ###

N, K = input().split()

dislike = set(list(map(int, input().split())))

next_map = {}
min_digit = 0
for i in range(10):
    for j in range(i,10):
        if j not in dislike:
            if i == 0:
                min_digit = j
            next_map.update({ i : j })
            break
        next_map.update({ i : min_digit })
max_digit = max(next_map.values())

num = len(list(N))
count = num
cand = []
for n in list(N):
    n = int(n)
    if n in dislike:
        n_ = next_map[n]
        cand.append(n_)
        count -= 1
        cand.extend(count*[min_digit])
        break
    else:
        cand.append(n)
        count -= 1
cand = int("".join(list(map(str, cand))))
if int(N) <= cand:
    print(cand)
else:
    if min_digit == 0:
        next_min = next_map[1]
        cand = [next_min] + num * [0]
    else:
        cand = (num + 1) * [min_digit]
    cand = int("".join(list(map(str, cand))))
    print(cand)
a, b = list(map(int, input().split()))

def gcd(num):
    k = []
    for i in [1,2]+list(range(3, num+1, 2)):
        if num%i == 0:
            k.append(i) 
    return k

def is_prime(num):
    for i in range(2, num):
        if num % i == 0:
            return False
    return True

ka = gcd(a)
kb = []
for i in ka:
  if b%i == 0:
    if is_prime(i):
        kb.append(i)

print(len(kb))

### FIXED CODE ###

def f(n):
    res = set()
    for i in range(2, int(n ** 0.5)):
        if n % i: continue
        while not n % i: n //= i
        res.add(i)
    return res | {n}
 
a, b = map(int,input().split())
print(len(f(a) & f(b) | {1}))
n=int(input())
ans =0
for i in range(1,n+1)
	for j in range(i,n+1,i) :ans+=j
print(ans)

### FIXED CODE ###

n=int(input())
ans =0
for i in range(1,n+1):
	for j in range(i,n+1,i) :ans+=j
print(ans)
(n,m,x)=map(int,input().split())
c=list()
a=list()
for i in range(n):
  line=list(map(int,input().split()))
  c.append(line.pop(0))
  a.append(line)

result=list()
for i in range(2**n):
  total=[0]*m
  cost=0
  for k in range(n):
    if bin(i)[k]=="1":
      total+=a[k]
      cost+=int(c[k])
  if total>=[x]*m:
    result.append(cost)

if result!=[]:
  print(min(result))
else:
  print(-1)

### FIXED CODE ###

import numpy as np
(n,m,x)=map(int,input().split())

a=list()
for i in range(n):
    line=list(map(int,input().split()))
    a.append(line)

a=np.array(a)
result=np.array([[0]*(m+1)])
for i in range(n):
    l=list()
    for j in range(len(result)):
        l.append(a[i]+result[j])
        l.append(result[j])
    result=np.array(l)

c=list()
h=[x]*m
for line in result:
    if np.all(line[1:]>=h):
        c.append(line[0])
if len(c)==0:
    print(-1)
else:
    print(min(c))
"
ABC162A
https://atcoder.jp/contests/abc162/tasks/abc162_a
"

# arr.include?(str) = arr内にstrが存在するか？(bool)
puts (gets.chomp.split("").include?("7")) ? "Yes" : "No"

### FIXED CODE ###

print("Yes" if ('7' in list(input())) else "No")
N,M,C=map(int,input().split())
B=list(map(int,input().split()))
X=0
Y=0
for i in range(N):
  A=list(map(int,input().split()))
  for i in range(N):
    Y+=A[i]*B[i]
  Y=Y+C
  if Y>0:
    X+=1
print(X)

### FIXED CODE ###

N,M,C=map(int,input().split())
B=list(map(int,input().split()))
X=0
for i in range(N):
  A=list(map(int,input().split()))
  Y=0
  for i in range(M):
    Y+=A[i]*B[i]
  Y=Y+C
  if Y>0:
    X+=1
  else:
    pass
print(X)
a=int(input())
b=input()
if b[0:a//2-1]==[a//2:a-1]:
  print('Yes')
else:
  print('No')

### FIXED CODE ###

a=int(input())
b=input()
if b[0:a//2]==b[a//2:]:
  print('Yes')
else:
  print('No')
def main():

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

    zzz=[]
    oioi=0
    flg=False

    for i in range(1,n+1):
        oioi = a[oioi]-1
        zzz.append(oioi)
        if oioi == 0:
            break
        if oioi in zzz:
            flg=True
            ppp=zzz.index(oioi)
            qqq=len(zzz)
            li=zzz
            del zzz[0:ppp+1]
            break


    
    if k>=qqq and flg:
        print(zzz[(k+ppp)%len(zzz)-1]+1)
    elif k<=qqq and flg:
        print(li[k-1]+1)
    else:    
        print(zzz[k%len(zzz)-1]+1)

    

if __name__ == '__main__':
    main()


### FIXED CODE ###

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

l = [1]
for i in range(n):
    l.append(a[l[i] - 1])

p = l.index(l[n])

if k <= n:
    print(l[k])
else:
    x = (k - n + 1) % (n - p)
    if x == 0:
        print(l[n - 1])
    else:
        print(l[x + p - 1])
import collections
def sortFirst(val):
    return val[0]
N=raw_input("")
N=int(N)
l={}
for i in range(1,N+1):
    S,P = raw_input("").split(' ')
    if S in l.keys():
        l[S].append([int(P),i])

    else:
        l[S]=[[int(P),i]]


for key in l.keys():
    l[key].sort(key=sortFirst,reverse=True)
for key in sorted(l):
    for val in l[key]:
        print "%d"%(val[1])


### FIXED CODE ###

from sys import stdin


def sortFirst(val):
    return val[0]
N=stdin.readline().rstrip()
N=int(N)
l={}
for i in range(1,N+1):
    S,P = stdin.readline().rstrip().split()
    if S in l.keys():
        l[S].append([int(P),i])

    else:
        l[S]=[[int(P),i]]


for key in l.keys():
    l[key].sort(key=sortFirst,reverse=True)
for key in sorted(l):
    for val in l[key]:
        print(val[1])
N,K = map(int,input().split())
p = list(map(int,input().split()))
p.sort()

print(p[0]+p[1]+p[2])

### FIXED CODE ###

N,K = map(int,input().split())
p = list(map(int,input().split()))
p.sort()
count = 0
if len(p) >= K:
    for i in range(K):
        count = count + p[i]
else:
    for i in p:
        count = count + i
        
print(count)
print(("None" if not x else x[0])(sorted(set(chr(97+i) for i in range(26))-set(input())))

### FIXED CODE ###

print((lambda x:"None" if not x else sorted(list(x))[0])(set([chr(i) for i in range(97,97+26)])-set(list(input()))))
a,b,c=input()
e=list(input(a))
f=list(input(b))
g=list(input(c))
print(e[0],f[0],g[0])

### FIXED CODE ###

a,b,c=input().split()
print(a[0][0]+b[0][0]+c[0][0])
def judgeAllBulbsOn(switchOn, conds, p):
  m = len(conds)
  flag = True
  for i in range(m):
    k = conds[i][0]
    numOfBulbOn = 0
    for i in range(k):
      if switchOn[conds[i][k]] == True:
        numOfBulbOn +=1
    if numOfBulbOn % 2 != p[m]:
      flag = False
      break
  return flag
      

#n:switch, m:bulb
n, m = map(int, input().split())

conds = []
for i in range(m):
  connect = list(map(int, input().split()))
  conds.append(connect)
  
p = list(map(int, input().split()))

switchOn = [False]*n

ans = 0
for bit in range(1<<n):
  for i in range(n):
    if bit & 1<<i == 1:
      switchOn[i] = True
    else:
      switchOn[i] = False
  if judgeAllBulbsOn(switchOn, conds, p):
    ans+=1
print(ans)

### FIXED CODE ###

def judgeAllBulbsOn(switchOn, conds, p):
    m = len(conds)
    bulbOnFlag = True
    for i in range(m):
        k = conds[i][0]
        numOfSwitchOn = 0
        for j in range(1, k + 1):

            # switchOn is 0 - index
            if switchOn[conds[i][j] - 1] is True:
                numOfSwitchOn += 1
        if numOfSwitchOn % 2 != p[i]:
            bulbOnFlag = False
            break
    return bulbOnFlag


# n:switch, m:bulb
n, m = map(int, input().split())

conds = []
for i in range(m):
    connect = list(map(int, input().split()))
    conds.append(connect)

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

switchOn = [False] * n

ans = 0
for bit in range(1 << n):
    for i in range(n):
        if bit & 1 << i:
            switchOn[i] = True
        else:
            switchOn[i] = False
    if judgeAllBulbsOn(switchOn, conds, p):
        ans += 1
print(ans)
import sys
sys.setrecursionlimit(100000000)

n = int(input())
x = input()

c1 = x.count('1')
cc1 = int('0b' + x, 0) % (c1 - 1)
cc2 = int('0b' + x, 0) % (c1 + 1)

def f(n):
    ans = 0
    while n > 0:
        ans += 1
        n = n % bin(n).count('1')
    return ans

for i in range(n):
    if x[i] == '1':
        print(f((-pow(2, n-i-1, c1-1) + cc1) % (c1 - 1)) + 1)
    else:
        print(f((pow(2, n-i-1, c1+1) + cc2) % (c1 + 1)) + 1)

### FIXED CODE ###

import sys
sys.setrecursionlimit(100000000)

n = int(input())
x = input()

c1 = x.count('1')
if c1 > 1:
    cc1 = int('0b' + x, 0) % (c1 - 1)
cc2 = int('0b' + x, 0) % (c1 + 1)

def f(n):
    ans = 0
    while n > 0:
        ans += 1
        n = n % bin(n).count('1')
    return ans

if c1 == 1:
    for i in range(n):
        if x[i] == '1':
            print(0)
        else:
            print(f((pow(2, n-i-1, c1+1) + cc2) % (c1 + 1)) + 1)
    exit()

for i in range(n):
    if x[i] == '1':
        print(f((-pow(2, n-i-1, c1-1) + cc1) % (c1 - 1)) + 1)
    else:
        print(f((pow(2, n-i-1, c1+1) + cc2) % (c1 + 1)) + 1)
*S = sorted(input().split(), reverse=True)
print(eval(S[0]+S[1]+ '+' + S[2]))

### FIXED CODE ###

abc = list(map(int, input().split()))
abc = list(reversed(sorted(abc)))

ans = abc[0]*10 + abc[1] + abc[2]
print(ans)
S=input()
n=len(S)
def T(i):
    if i == 0:
        return 0
    else:
        i-=1
        return T(i)+(10**i)*int(S[n-1-i])
s=[0]*2018
for j in range(1,n+1):
    print(T(j))
    m=T(j)%2019
    s[m]+=1

c=s[0]

for m in s:
    c += m*(m-1)/2

print(int(c))

### FIXED CODE ###

s = input()
p = 2019
n = 0
ans = 0
mods = [0]*p
mods[0] = 1
for i, j in enumerate(reversed(s)):
  n += int(j)*pow(10, i, p)
  n %= p
  mods[n] += 1
for i in mods:
  ans += i*(i-1)//2
print(ans)
import sys
import math
N=int(input())
A=list(map(int,input().split()))


def sieve_of_eratosthenes(n): #エラトステネスのふるい
    candidate = list(range(2, n+1)) #候補
    prime = []
    limit = n**0.5 + 1 #+1がないと平方数を素数にしてしまう

    while True:
        p = candidate[0] 
        if limit <= p:
            prime.extend(candidate) #この時点での残っているのは素数
            break
        prime.append(p) #pを素数リストに登録

        candidate = [i for i in candidate if i % p != 0]

        # i = 0
        # while True:
            # if i >= len(candidate): #iはcandidateの長さ分
                # break
            # elif candidate[i] % p == 0: #余りがゼロなら
                # candidate.pop(i) #素数ではないのでpop(取り除く)する
            # i += 1

    return prime



maxA=max(A)

prime = sieve_of_eratosthenes(maxA)

X=[0]*(maxA+1)
for i in range(N):
    X[A[i]]+=1

check=0
for i in prime:
    count=0
    for j in range(1,int(maxA/i)+1):
        count+=X[j*i]
    if count==N:
        print('not coprime')
        sys.exit()
    elif count>1:
        check=1
        
if check==1:
    print('setwise coprime')
else:
    print('pairwise coprime')

### FIXED CODE ###

N, M=map(int, input().split())
A=[]
B=[]
for i in range(M):
    a,b=map(int, input().split())
    A.append(a)
    B.append(b)
# AB= [map(int, input().split()) for _ in range(M)]
# A, B = [list(i) for i in zip(*AB)]
def find(x,parent):
    if parent[x]==x:
        return x
    else:
        parent[x]=find(parent[x],parent)
        return(parent[x])
        
def union(x,y,parent,rank):
    xroot=find(x,parent)
    yroot=find(y,parent)
    if rank[xroot]>rank[yroot]:
        parent[yroot]=xroot
    elif rank[yroot]>rank[xroot]:
        parent[xroot]=yroot
    elif rank[yroot]==rank[xroot]:
        parent[yroot]=xroot
        rank[xroot]+=1
    return(parent,rank)

    
parent=[i for i in range(N+1)]
rank=[0]*(N+1)
for i in range(M):
    parent,rank=union(A[i],B[i],parent,rank)
for i in range(N+1):
    find(i,parent)
G=parent[1:]
import collections
c=collections.Counter(G)
print(int(c.most_common()[0][1]))
import io
import sys


def IN_S():
  return input()


def IN_I():
  return int(input())


def IN_L_I():
  return list(map(int, input().split()))


def IN_L_S():
  return list(map(str, input().split()))


def STR_SPLIT(s, n):
  for l in range(0, len(s), n):
    yield s[0 + l:n + l]


def T_IN():
  global test_str
  sys.stdin = io.StringIO(test_str[1:-1])


test_str = '''
5
5
4
3
5
2
1
'''


def MAIN():
  T_IN()
  A()


def A():
  n = IN_I()

  l = []
  
  snum = -1
  pnum = -1
  for i in range(0, n):
    num = IN_I()
    # print("num:", num )
    if pnum < num:
      pnum = num
      continue

    # print(l, num)
    for j in range(0, len(l) + 1):
      # print(j, len(l))
      if j == len(l):
        # print("l append", pnum)
        l.append(pnum)
      else:
        if l[j] < snum:
          l[j] = pnum
          print (l[j], pnum)
          break

    # print ("pnum", num)
    snum = pnum = num

  if pnum > -1:
    for j in range(0, len(l) + 1):
      if j == len(l):
        l.append(pnum)
      else:
        if l[j] < snum:
          l[j] = pnum
          break

  print(len(l))
  return None


def B():
  return None


def C():
  return None


MAIN()


### FIXED CODE ###

import io
import sys
from bisect import bisect_right, bisect_left
from collections import deque


def IN_S():
  return input()


def IN_I():
  return int(input())


def IN_L_I():
  return list(map(int, input().split()))


def IN_L_S():
  return list(map(str, input().split()))


def STR_SPLIT(s, n):
  for l in range(0, len(s), n):
    yield s[0 + l:n + l]


def T_IN():
  global test_str
  sys.stdin = io.StringIO(test_str[1:-1])


test_str = '''
7
1
0
3
4
1
2
1
'''


def MAIN():
  # T_IN()
  A()


def A():
  n = IN_I()

  l = deque([IN_I()])

  for i in range(0, n - 1):
    num = IN_I()

    idx = bisect_left(l, num)
    if idx == 0:
      l.appendleft(num)
    else:
      l[idx - 1] = num
    # print(l)

  print(len(l))
  return None


def B():
  return None


def C():
  return None


MAIN()
n, m = map(int, input().spllit())
tmp = abs(n)-abs(m)
print(tmp if (n <= 0 and m <= 0) or  (n >= 0 and m >= 0) else tmp+1)


### FIXED CODE ###

x, y = map(int, input().split())
tmp = abs(abs(x) - abs(y))
if (y == 0 and 0 < x) or (x == 0 and y < 0):
    print(tmp + 1)
elif 0 <= x * y and x <= y:
    print(tmp)
elif 0 <= x * y and y < x:
    print(tmp + 2)
else:
    print(tmp + 1)
if 13 <= A:
    print(B)
elif (6 <= A) and (A<=12):
    print(B/2)
else:
    print(0)

### FIXED CODE ###

A,B = map(int,input().split())

if 13 <= A:
    print(B)
elif (6 <= A) and (A<=12):
    print(B//2)
else:
    print(0)
#!/usr/bin/env python
# -*- coding: utf-8 -*-

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

count = 0
i = 1
while i <= (N-1):
    if A[i] == A[i - 1]:
        j = i + 1
        if j <= (N-1):
            while True:
                if A[j] == A[j - 1]:
                    count += 1
                    j += 1
                else:
                    count += 2
                    i = j
                    break
        else:
            count += 2
            break
    else:
        i += 1

print(count // 2)


### FIXED CODE ###

#!/usr/bin/env python
# -*- coding: utf-8 -*-

N = int(input())
A = [int(i) for i in input().split()] + [0]

count = 0
tmp = 1
for i in range(1, N+1):
    if A[i] == A[i - 1]:
        tmp += 1
    else:
        # 等しくなくなったら
        count += tmp // 2
        tmp = 1  # tmp のリセット

print(count)
a, b = map(int, input().split())
print([':(', 'Yay!'][int((a <= 16) & (b <= 8)])


### FIXED CODE ###

a, b = map(int, input().split())
print([':(', 'Yay!'][int((a <= 8) & (b <= 8))])