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

ai = lambda: list(map(int, input().split()))

n, m = ai()

from collections import defaultdict as dd

edge = dd(list)
for _ in range(m):
    a, b, c = ai()
    edge[a - 1].append([b - 1, -c])

dist = [float('inf')] * n
dist[0] = 0
vs = {0}
i = 0
while vs:
    cur_v = vs.pop()
    for v, c in edge[cur_v]:
        if dist[v] > dist[cur_v] + c:
            dist[v] = dist[cur_v] + c
            vs.add(v)
            if i > n and v == n - 1:
                print('inf')
                exit()
    i += 1

print(-dist[-1])

### FIXED CODE ###

ai_ = lambda: [int(x)-1 for x in input().split()]
ai = lambda: list(map(int, input().split()))

n,m = ai()

from collections import defaultdict as dd
edge = dd(list)
for _ in range(m):
    a,b,c = ai()
    edge[a-1].append([b-1, -c])

dist = [float('inf')] * n
dist[0] = 0

for i in range(n):
    for cur_v in range(n):
        for v, c in edge[cur_v]:
            if dist[v] > dist[cur_v] + c:
                dist[v] = dist[cur_v] + c
                if i == n-1 and v == n-1:
                    print('inf')
                    exit()
print(-dist[-1])
### BUGGY CODE ###

from math import sqrt

s = int(input())
n=int(sqrt(s))
x1=0
y1=0
y2=0
x3=0
for i in range(n):
    if s%(n-i)==0:
        x2=s//(n-i)
        y3=n-i
        break
print(x1,y1,x2,y2,x3,y3)


### FIXED CODE ###

n = int(input())
N = 10**9
x1=0
y1=0
x2=N
y2=1
x3=N-n%N
y3=n//N+1
if n==10**18:
    x3=0
    y3=n//N

print(x1,y1,x2,y2,x3,y3)
### BUGGY CODE ###

import numpy as np

N = int(input())
A = np.sort(np.array(list(map(int, input().split()))))
b = np.ones(N, dtype=bool)
for i, ai in enumerate(A):
    if b[i] == 0:
        continue
    b[b] = (A[b] % ai != 0)
    b[i] = (i==N-1) or (A[i]!=A[i+1])
print(b.sum())


### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
maxA = max(A)
counter = [0]*(maxA+1)
for ai in A:
    for m in range(ai, maxA+1, ai):
        counter[m] += 1
ans = 0
for ai in A:
    ans += (counter[ai] == 1)
print(ans)
### BUGGY CODE ###

k=int(input())

# mod k で考える
mod=k

for i in range(1,k+2):
    if mod>7*int(str(1)*i):
        continue
    else:
        if mod==k:
            mod = 7 * int(str(1) * i) % mod
            if mod == 0:
                print(i)
                exit()
        else:
            mod= (mod*10+7)%k
            if mod==0:
                print(i)
                exit()

print(-1)

### FIXED CODE ###

k=int(input())

cur=0
for i in range(k+2):
    cur=(cur*10+7)%k
    if cur==0:
        print(i+1)
        exit()

print(-1)
### BUGGY CODE ###

import itertools

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

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

ans = []
for v in itertools.combinations(p,K):
    ans.append(sum(v))
    
print(min(ans))

### FIXED CODE ###

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

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

s = sorted(p)

ans = 0 
for i in range(N):
    ans += s[i]
    if i == K-1:
        break

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

n,k=map(int,input().split())
l=tuple(map(int,input().split()))
dp=[-1]*(n+1)
dp[1]=0
for i in range(2,min(n,k)+1):
  dp[i]=abs(l[i-1]-l[0])
if k>=n:
  print(dp[n])
else:
  dp[k+1]=abs(l[0]-l[k])
  for i in range(k+2,n+1):
    min=10**10
    for j in range(i-k,i):
      if min>dp[j]+abs(l[j-1]-l[i-1]):
        min=dp[j]+abs(l[j-1]-l[i-1])
    dp[i]=min
  print(dp[n])


### FIXED CODE ###

n,k=map(int,input().split())
l=tuple(map(int,input().split()))
dp=[-1]*(n+1)
dp[1]=0
for i in range(2,min(n,k)+1):
  dp[i]=abs(l[i-1]-l[0])
if k>=n:
  print(dp[n])
else:
  dp[k+1]=abs(l[0]-l[k])
  for i in range(k+2,n+1):
    min=10**10
    for j in range(i-k,i):
      if min>dp[j]+abs(l[j-1]-l[i-1]):
        min=dp[j]+abs(l[j-1]-l[i-1])
    dp[i]=min
  print(dp[n])
### BUGGY CODE ###

s = input()
i = 0
c = 0
for _ in range(10**8):
    if len(s)==0 or i == len(s)-1:
        break
    if s[i] != s[i+1]:
        s = s[:i]+s[i+2:]
        c += 1
        i = 0
        continue
    i += 1
print(c*2)

### FIXED CODE ###

s = input()
print(min(s.count("1"),s.count("0"))*2)
### BUGGY CODE ###

N=int(input())
A=list(map(int,input().split()))
L=[]
R=[]
ans=0
for i in range(N):
    L.append(i+1+A[i])
    R.append(i+1-A[i])
L.sort()
R.sort()
l=0
for i in range(N):
    if i>=1:
        if L[i]==L[i-1]:
            ans=ans+count
            continue
    count=0
    for j in range(l,N):
        if L[i]==R[j]:
            count=count+1
        if L[i]<R[j]:
            l=j
            break
    ans=ans+count
print(ans)

### FIXED CODE ###

import bisect
N=int(input())
A=list(map(int,input().split()))
L=[]
R=[]
ans=0
for i in range(N):
    L.append(i+1+A[i])
    R.append(i+1-A[i])
L.sort()
R.sort()
for i in L:
    l=bisect.bisect_left(R,i)
    r=bisect.bisect_right(R,i)
    ans=ans+r-l
print(ans)
### BUGGY CODE ###

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

def solve(s,n):
    if "W" not in s or "R" not in s:
        return 0
    if s.find("WR")==-1:
        return 0
    else:
        arr=list(s)
        i=0
        j=len(s)-1
        count=0
        r=s.count("R")
        w=s.count("W")
        s1="R"*r+"W"*w
        brr=list(s1)

        while arr!=brr:
            if arr[i]=="W":
                if arr[j]=="R":
                    count += 1
                    arr[i]="R"
                    arr[j]="W"
                    i+=1
                    j-=1

                else:
                    j-=1
            else:
                if arr[j]=="R":
                    i+=1
                else:
                    i+=1
                    j-=1
        return count
print(solve(s,n))





### FIXED CODE ###

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

def solve(s,n):
    if "W" not in s or "R" not in s or s.find("WR")==-1:
        return 0

    else:
        arr=list(s)
        i=0
        j=n-1
        count=0

        while i<j:
            if arr[i]=="W" and arr[j]=="R":
                count += 1
                i+=1
                j-=1

            elif arr[i]=="W" and arr[j]=="W":
                j-=1
            elif arr[i]=="R" and arr[j]=="R":

                i+=1
            else:
                i+=1
                j-=1
        return count
print(solve(s,n))
### BUGGY CODE ###

n=int(input())
ans=0
l=[]
for i in range(n):
    l.append(sorted(input()))

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

### FIXED CODE ###

n=int(input())
l=[]
for i in range(n):
    s = input()
    s = sorted(s)
    l.append(''.join(s))
l.sort()
sa = l[0]
cnt = 0
n = 1
for sb in l[1:]:
  if sb == sa:
    n += 1
  else:
    cnt += (n * (n-1) // 2)
    n = 1
    sa = sb
cnt += (n * (n-1) // 2)
print(cnt)
### BUGGY CODE ###

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

a=input().split()

l=len(a)

for i in range(0,l):
    a[i]=int(a[i])

p=1
for i in range(0,k):
    p=a[p-1]

print(p)


### FIXED CODE ###

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


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

ar=[-1 for i in range(n+1)]
p=1

go=0


for i in range(1,k+1):
    
    
    
    

    ar[p]=i-1
    p=a[p-1]
    
    if ar[p]>0:
        j=ar[p]
        amari=(k-i)%(i-j)
        
        go=1
        break

if go==1:
    p=ar.index(j+amari)
    
    


print(p)
### BUGGY CODE ###

import itertools

n = int(input())
l = [int(v) for v in input().split()]

l = sorted(l)

comb = list(itertools.combinations(l, 3))
count = 0
for i in range(len(comb)):
    a = comb[i][0]
    b = comb[i][1]
    c = comb[i][2]
    if a + b <= c:
        continue
    elif a + c <= b:
        continue
    elif b + c <= a:
        continue
    else:
        count += 1

print(count)

### FIXED CODE ###

import bisect


def triangles():
    n = int(input())
    l = [int(v) for v in input().split()]
    l.sort()

    count = 0
    for i in range(n):
        for j in range(i + 1, n):
            c = l[i] + l[j]
            index = bisect.bisect_left(l, c)
            count += max(index - j - 1, 0)

    print(count)


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

#coding: UTF-8

x=int(input())

i=1

while x !=0:
    print('Case {}: {}'.format(i,x))
    i=i+1



### FIXED CODE ###

c = 0

while True:
    x = int(input())
    c +=1
    
    if x == 0:
        break
   
    print("Case {}: {}".format(c, x))
### BUGGY CODE ###

n, m = map(int, input().split())
py_dict = {}
cityi_by_year = []
for i in range(m):
  p, y = map(int, input().split())
  if p not in py_dict:py_dict[p] = [y]
  else:py_dict[p].append(y)
  cityi_by_year.append(y)

ans = [-1 for _ in range(m)]
for p in sorted(py_dict.keys()):
  p_str = '0'*(6-len(str(p))) + str(p)
  cnt = 0
  for y in sorted(py_dict[p]):
    cnt += 1
    ans[cityi_by_year.index(y)] = p_str + '0'*(6-len(str(cnt))) + str(cnt)
[print(id) for id in ans]

### FIXED CODE ###

import collections
import bisect
n,m=map(int,input().split())
p=[[int(j) for j in input().split()] for i in range(m)]
a=collections.defaultdict(list)
for x,y in sorted(p):
    a[x]+=[y]
for x,y in p:
    z=bisect.bisect(a[x],y)
    print("%06d%06d"%(x,z))
### BUGGY CODE ###

n=int(input())

A=[]
B=[]
for i in range(n):
  s=input()
  if s not in B:
    A.append([1,s])
    B.append(s)
  else:
    A[B.index(s)][0] += 1
A=sorted(A,reverse=True)
A.sort(key=lambda x:(x[0], x[1]), reverse=True)

C=[]
for i in range(len(A)):
  C.append(A[i][1])
  if i == len(A)-1:
    break
  if A[i][0] != A[i+1][0]:
    break
C.sort()
for i in range(len(C)):
  print(C[i])


### FIXED CODE ###

import collections
n = int(input())
s = []
for _ in range(n):
    s.append(input())

c = collections.Counter(s)
m = c.most_common()[0]

ans = []
for _c in c.items():
    if _c[1] == m[1]:
        ans.append(_c[0])

for v in sorted(ans):
    print(v)
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
A_ = sorted(A)
ans = ['']*N
for i in range(N):
  ans[i] = (str(A.index(A_[i])+1))
print(' '.join(ans))

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
ans = ['']*N
for id,name in enumerate(A):
  ans[name-1] = str(id+1)
print(' '.join(ans))
### BUGGY CODE ###

N = int(input())
 
def calculate_n(x, y, z):
  n = x**2 + y**2 + z**2 + x*y + y*z + z*x
  return n
l = []
for x in range(1, N):
  for y in range(1, N):
    for z in range(1, N):
      n = calculate_n(x,y,z)
      if n > N:
        break
      else:
        l.append(n)
    if calculate_n(x, y+1, 1) > N:
      break
  if calculate_n(x+1, 1, 1) > N:
    break
    
numbers = sorted(set(l))
counts = [l.count(x) for x in numbers]
d = dict(zip(numbers, counts))
 
for i in range(1, N+1):
  if i in d:
  	print(d[i])
  else:
    print(0)

### FIXED CODE ###

N = int(input())
 
def calculate_n(x, y, z):
  n = x**2 + y**2 + z**2 + x*y + y*z + z*x
  return n
l = []
for x in range(1, N):
  for y in range(1, N):
    for z in range(1, N):
      n = calculate_n(x,y,z)
      if n > N:
        break
      else:
        l.append(n)
    if calculate_n(x, y+1, 1) > N:
      break
  if calculate_n(x+1, 1, 1) > N:
    break

import collections
c = collections.Counter(l)
for i in range(1, N+1):
  if i in c:
    print(c[i])
  else:
    print(0)
### BUGGY CODE ###

#Trained?
N = int(input())
a = [int(input()) for _ in range(N)]
judge2 = 0
judgeloop = 0
now = 1
tugi = a[0]
rireki = []
n = 1

if tugi == 2:
    judge2 += 1

while judge2 == 0 and judgeloop == 0:
    n += 1
    rireki.append(now)
    now = tugi
    tugi = a[tugi-1]
    if tugi in rireki:
        judgeloop += 1
    elif tugi == 2:
        judge2 += 1

if judgeloop == 1:
    print(-1)
elif judge2 == 1:
    print(n)

### FIXED CODE ###

#Trained?
N = int(input())
a = [int(input()) for _ in range(N)]

now = 1
L = [0]*N
for i in range(N):
    L[i] = now
    now = a[now-1]

judge = 1
for i in range(N):
    if L[i] == 2:
        print(i)
        judge = 0
        break
    else:
        pass

if judge == 1:
    print(-1)
### BUGGY CODE ###

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

for i in range(M):
    ind = A.index(max(A))
    A[ind] = A[ind]/2
    # print(A)

A =list(map(int,A))
print(sum(A))

### FIXED CODE ###

from heapq import heappush,heappop,heapify
N,M= map(int,input().split())
A = list(map(int,input().split()))
a = [-x for x in A]
heapify(a)
for i in range(M):
    item = -1*heappop(a)
    item = item//2
    heappush(a,-1*item)
print(-sum(a))
### BUGGY CODE ###

h,w = map(int,input().split())
s = []
v = [(1, 0), (0, 1), (-1, 0), (0, -1)]
for i in range(h):
    s += [input()]
ans = 0


def dfs(d, i, j, c):
    if i < 0 or h <= i or j < 0 or w <= j:
        return
    if s[i][j] == '#' or d[i][j] <= c:
        return

    d[i][j] = c
    for y,x in v:
        dfs(d, i+y, j+x, c+1)


for i in range(h*w): 
    for j in range(h*w):
        d = [[h * w] * w for i in range(h)]
        p = (i // w, i % w)
        q = (j // w, j % w)
        if s[p[0]][p[1]] == '#' or s[q[0]][q[1]] == '#':
            continue
        dfs(d, p[0], p[1], 0)
        if d[q[0]][q[1]] < h*w:
            ans = max(d[q[0]][q[1]], ans)

print(ans)

### FIXED CODE ###

import queue
h,w = map(int,input().split())
v = [(1, 0), (0, 1), (-1, 0), (0, -1)]
s = [input() for i in range(h)]

ans = 0
que = queue.Queue()
for i in range(h * w):
    c = 0
    d = [[h*w] * w for i in range(h)]
    p = (i//w, i%w)
    if s[p[0]][p[1]] == '#':
        continue
    d[p[0]][p[1]] = 0
    que.put(p)
    while not que.empty():
        y,x = que.get()
        c = d[y][x]
        for dy, dx in v:
            yy = y + dy
            xx = x + dx
            if yy < 0 or xx < 0 or h <= yy or w <= xx:
                continue
            if s[yy][xx] == '#':
                continue
            if d[yy][xx] < h*w:
                continue
            que.put((yy, xx))
            d[yy][xx] = c + 1
    ans = max(ans, c)
print(ans)
### BUGGY CODE ###

from heapq import heappush, heappop

n, m = map(int, input().split())
edge = [list(map(int, input().split())) for _ in range(m)]
edge.sort()

q = []
for l, r, c in edge:
    # print(q)

    if l == 1:
        heappush(q, (r, c))
    else:
        q2 = []
        cand = float("inf")
        while q:
            y, z = heappop(q)

            if y < l:
                continue
            elif y < r:
                cand = min(cand, z)
                heappush(q2, (y, z))
            else:
                heappush(q2, (y, z))

        if cand != float("inf"):
            heappush(q2, (r, cand + c))

        q = q2
# print(q)

if len(q) == 0:
    ans = -1
else:
    ans = -1
    for y, z in q:
        if y == n:
            if ans == -1:
                ans = z
            else:
                ans = min(ans, z)

print(ans)


### FIXED CODE ###

from heapq import heappush, heappop
import sys
input = sys.stdin.readline


def dijkstra(graph: list, node: int, start: int) -> list:
    # graph[node] = [(cost, to)]
    INF = float('inf')
    dist = [INF] * node

    dist[start] = 0
    heap = [(0, start)]
    while heap:
        cost, thisNode = heappop(heap)
        for NextCost, NextNode in graph[thisNode]:
            dist_cand = dist[thisNode] + NextCost
            if dist_cand < dist[NextNode]:
                dist[NextNode] = dist_cand
                heappush(heap, (dist[NextNode], NextNode))
    return dist
    # dist = [costs to nodes]


n, m = map(int, input().split())
edge = [[] for _ in range(n)]
for _ in range(m):
    l, r, c = map(int, input().split())
    l -= 1
    r -= 1
    edge[l].append((c, r))
for i in range(1, n):
    edge[i].append((0, i - 1))

dist = dijkstra(edge, n, 0)
ans = dist[-1] if dist[-1] != float("inf") else -1

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

L,R = map(int,input().split())
list_LR = range(L,R+1)

list_aaa =[]

for i in range(L,R+1):
    for j in range(i+1,R+1):
        list_aaa.append((i*j)%2019)


print(min(list_aaa))


### FIXED CODE ###

L,R = map(int,input().split())
list_LR = range(L,R+1)

list_aaa =[]

ans = 2019
l=min(L+2019, R+1)

for i in range(L,l):
    for j in range(i+1,l):
        ans = min(ans,(i*j)%2019)

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

from collections import defaultdict

n, p = map(int, input().split())
S = input().strip()

if p == 2 or p == 5:
    count = 0
    digits = '02468' if p == 2 else '05'
    for i, x in enumerate(S, 1):
        if x in digits:
            count += i
    print(count)
else:
    def comb(n):
        if n >= 2:
            return n*(n-1) // 2
        else:
            return 0
    
    counter = [0]*p
    for i in range(n-1, -1, -1):
        counter[int(S[i:]) % p] += 1
    print(counter[0] + sum(int(comb(i)) for i in counter))

### FIXED CODE ###

n, p = map(int, input().split())
if p in (2, 5):
  c = 0
  for i, x in enumerate(map(int, input()[::-1])):
    if x % p == 0:
      c += n-i
  print(c)
else:
  c = [0] * p
  y = 0
  t = 1
  for x in map(int, input()[::-1]):
    y = (y + t*x) % p
    c[y] += 1
    t = (10 * t) % p
  print(sum(i * (i-1) // 2 for i in c) + c[0])
### BUGGY CODE ###

N, M = map(int, input().split())
node_num = N
route_list = [[10**9 + 1] * N for _ in range(N)]
for i in range(M):
    L, R, C = map(int, input().split())
    route_list[L-1][R-1] = min(C, route_list[L-1][R-1])
for i in range(N-1):
    route_list[i+1][i] = 0
unsearched_nodes = list(range(node_num))
distance = [10**9] * node_num
previous_nodes = [-1] * node_num
distance[0] = 0


def get_target_min_index(min_index, distance, unsearched_nodes):
    start = 0
    while True:
        index = distance.index(min_index, start)
        found = index in unsearched_nodes
        if found:
            return index
        else:
            start = index + 1


while(len(unsearched_nodes) != 0):
    # まず未探索ノードのうちdistanceが最小のものを選択する
    posible_min_distance = 10**9
    for node_index in unsearched_nodes:
        if posible_min_distance > distance[node_index]:
            posible_min_distance = distance[node_index]
    target_min_index = get_target_min_index(posible_min_distance, distance, unsearched_nodes)
    unsearched_nodes.remove(target_min_index)

    target_edge = route_list[target_min_index]
    for index, route_dis in enumerate(target_edge):
        if route_dis <= 10**9:
            if distance[index] > (distance[target_min_index] + route_dis):
                distance[index] = distance[target_min_index] + route_dis
                previous_nodes[index] = target_min_index

if distance[node_num - 1] == 10**9:
	print(-1)
else:
    print(distance[node_num - 1])

### FIXED CODE ###

from heapq import heappop, heappush
N, M = map(int, input().split())
route_list = [[] for _ in range(N)]
for i in range(M):
    L, R, C = map(int, input().split())
    route_list[L-1].append((R-1, C))
for i in range(N-1):
    route_list[i+1].append((i, 0))

distance = [float("inf")] * N
distance[0] = 0  # 初期のノードの距離は0とする
q = [(0, 0)]

while q:
    _, u = heappop(q)
    for des, cost in route_list[u]:
        if distance[des] > distance[u] + cost:
            distance[des] = distance[u] + cost
            heappush(q, (distance[des], des))

print(distance[-1] if distance[-1] != float("inf") else -1)
### BUGGY CODE ###

from sys import stdin
nii=lambda:map(int,stdin.readline().split())
lnii=lambda:list(map(int,stdin.readline().split()))
from collections import Counter

h,w,m=nii()

h_bomb=[0 for i in range(h)]
w_bomb=[0 for i in range(w)]

l=[]
for i in range(m):
  th,tw=nii()
  th-=1
  tw-=1
  h_bomb[th]+=1
  w_bomb[tw]+=1
  l.append([th,tw])

h_max=max(h_bomb)
w_max=max(w_bomb)

h_cand=[]
w_cand=[]

for i in range(len(h_bomb)):
  if h_bomb[i]==h_max:
    h_cand.append(i)

for i in range(len(w_bomb)):
  if w_bomb[i]==w_max:
    w_cand.append(i)

ans=0
for i in h_cand:
  for j in w_cand:
    if [i,j] in l:
      ans=max(ans,h_max+w_max-1)
    else:
      ans=max(ans,h_max+w_max)

print(ans)

### FIXED CODE ###

from sys import stdin
nii=lambda:map(int,stdin.readline().split())
lnii=lambda:list(map(int,stdin.readline().split()))
from collections import Counter

h,w,m=nii()

h_bomb=[0 for i in range(h)]
w_bomb=[0 for i in range(w)]

l=set()
for i in range(m):
  th,tw=nii()
  th-=1
  tw-=1
  h_bomb[th]+=1
  w_bomb[tw]+=1
  l.add((th,tw))

h_max=max(h_bomb)
w_max=max(w_bomb)

h_cand=[]
w_cand=[]

for i in range(len(h_bomb)):
  if h_bomb[i]==h_max:
    h_cand.append(i)

for i in range(len(w_bomb)):
  if w_bomb[i]==w_max:
    w_cand.append(i)

for i in h_cand:
  for j in w_cand:
    if (i,j) not in l:
      print(h_max+w_max)
      exit()

print(h_max+w_max-1)
### BUGGY CODE ###

N, Q = map(int, input().split())
S = input()
list = []
for i in range(Q):
    l,r = map(int, input().split())
    list.append([l,r])

for i in range(Q):
    sub_S = S[list[i][0]-1:list[i][1]]
    count = 0
    for j in range(len(sub_S)-1):
        if sub_S[j] == 'A':
            if sub_S[j:j+2] == 'AC':
                count += 1
    print(count)

### FIXED CODE ###

N, Q = map(int, input().split())
S = input()
list = [[0 for i in range(2)] for j in range(Q)]

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

K,S= list(map(int, input().split()))
ans=0
for i in range(S//3,K+1):
    for j in range(i+1):
        if i+j>S:
            break
        if i+j*2<S:
            continue
        for k in range(j+1):
            if i+j+k==S:
                if i==j==k:
                    ans+=1
                elif i==j or j==k:
                    ans+=3
                else:
                    ans+=6
                break
print(ans)

### FIXED CODE ###

K,S= list(map(int, input().split()))
ans=0
for i in range(S//3,K+1):
    for j in range(i+1):
        if i+j>S:
            break
        if i+j*2<S:
            continue
        if S-i-j<=j:
            k=S-i-j
            if i==j==k:
                ans+=1
            elif i==j or j==k:
                ans+=3
            else:
                ans+=6
print(ans)
### BUGGY CODE ###

n = int(input())
A = [list(map(int, input().split())) for i in range(n)]
p = 10**9+7
DP = [None for s in range(1 << n)]
DP[0] = 1
def dp(s, l):
    if DP[s] != None:
        return DP[s]
    tmp = 0
    for i in range(n):
        if s & (1 << i) and A[l-1][i]:
            tmp += dp(~(1 << i) & s, l-1)
    DP[s] = tmp % p
    return DP[s]
print(dp((1 << n)-1, n))


### FIXED CODE ###

def main():
    n = int(input())
    A = [list(map(int, input().split())) for i in range(n)]
    p = 10**9+7
    DP = [0 for s in range(1 << n)]
    DP[0] = 1
    for s in range(1, 1 << n):
        l = bin(s).count('1')
        for i in range(n):
            if ((1 << i) & s) * A[l-1][i]:
                DP[s] += DP[~(1 << i) & s]
    print(DP[(1 << n)-1] % p)


main()
### BUGGY CODE ###

import bisect
import sys
sys.setrecursionlimit(1000000)

input = sys.stdin.readline

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

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

ans = [0] * n
visited = [0] * n
visited[0] = 1


def dfs(i, l):
    s = a[i]
    if len(l) == 0 or s > l[-1]:
        l.append(s)
    else:
        l[bisect.bisect_left(l, s)] = s
    ans[i] = len(l)

    for ni in tree[i]:
        if not visited[ni]:
            visited[ni] = 1
            dfs(ni, l[:])


dfs(0, [])

for i in ans:
    print(i)


### FIXED CODE ###

import bisect
import sys
sys.setrecursionlimit(1000000)

input = sys.stdin.readline

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

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

ans = [0] * n
visited = [0] * n
visited[0] = 1
l = []

def dfs(i):
    s = a[i]
    pi = -1
    pv = -1
    if len(l) == 0 or s > l[-1]:
        l.append(s)
    else:
        pi = bisect.bisect_left(l, s)
        pv = l[pi]
        l[pi] = s
    ans[i] = len(l)

    for ni in tree[i]:
        if not visited[ni]:
            visited[ni] = 1
            dfs(ni)
            
    if pi == -1:
        l.pop()
    else:
        l[pi] = pv


dfs(0)

for i in ans:
    print(i)