Harryxun/stf_run huggingface dataset:
def solve():
    n = int(input())
    al = [int(i) for i in input().split()]
    memos = [0]*n
    for i in range(n):
        memos[i] = i - (al[i] - 1)
    # print(memos)
    ans = 0
    for idx in range(n):
        while memos[idx] == 0:
            if idx == 0:
                memos[idx], memos[idx+1] = memos[idx+1]-1, memos[idx]+1
            elif idx == n-1:
                memos[idx], memos[idx+1] = memos[idx+1]-1, memos[idx]+1
            else:
                if memos[idx-1] > memos[idx+1]:
                    memos[idx-1], memos[idx] = memos[idx]-1, memos[idx-1]+1
                else:
                    memos[idx], memos[idx+1] = memos[idx+1]-1, memos[idx]+1
            ans += 1
        # print(memos)
    print(ans)

if __name__=="__main__":
    solve()


### FIXED CODE ###

def solve():
    n = int(input())
    al = [int(i) for i in input().split()]
    memos = [0]*n
    for i in range(n):
        memos[i] = i - (al[i] - 1)
    # print(memos)
    ans = 0
    for idx in range(n):
        if memos[idx] == 0:
            if idx != n - 1:
                memos[idx+1], memos[idx] = memos[idx+1]-1, memos[idx]+1
            else:
                memos[idx], memos[idx-1] = memos[idx-1]+1, memos[idx]-1
            ans += 1
        # print(memos)
    print(ans)

if __name__=="__main__":
    solve()
N = int(input())
S = list(input())
ans = S.count('R')*S.count('G')*S.count('B') 
for i in range(N): 
   if S[i]=='R':
       S[i]=1
   elif S[i]=='G':
       S[i]
   elif S[i]=='B':
       S[i]=4
for i in range(N): 
   for j in range(i+1,N):
     k=2*j-i
     if k>=N : 
       continue  
     if S[i]+S[j]+S[k]==7 : 
         ans-=1   
print(ans)

### FIXED CODE ###

N = int(input())
S = list(input())
ans = S.count('R')*S.count('G')*S.count('B') 
for i in range(N): 
   if S[i]=='R':
       S[i] =1
   elif S[i]=='G':
       S[i] =2
   elif S[i]=='B':
       S[i] =4
for i in range(N): 
   for j in range(i+1,N):
     k=2*j-i
     if k>=N : 
       continue  
     if S[i]+S[j]+S[k]==7 : 
         ans-=1 
print(ans)
import math

a, b, c, d = map(int,input().split())
cn_l, cn_r, cn_d = 0,0,0
l_list = []
r_list = []
if a%c == 0:
    start_l = a//c
else:
    start_l = a//c+1
# print('left')
cn_l = b//c+1 - start_l
# for i in range(start_l, b//c+1):
#     l_list.append(c*i)
#     cn_l += 1
if a%d == 0:
    start_r = a//d
else:
    start_r = a//d+1
# print('right')
cn_r = b//d+1 - start_r
# for i in range(start_r, b//d+1):
#     r_list.append(d*i)
#     cn_r += 1
# print(cn_l, cn_r)
# for val in l_list:
#     if val in r_list:
#         cn_d +=1
def lcm(x, y):
    return (x * y) // math.gcd(x, y)
lcm = lcm(c,d)
if a%lcm == 0:
    start_d = a//lcm
else:
    start_d = a//lcm+1
cn_d = b//lcm+1 - start_d
n = b-a+1
print(n-(cn_l+cn_r-cn_d))



### FIXED CODE ###

from fractions import gcd

a, b, c, d = map(int,input().split())
cn_l, cn_r, cn_d = 0,0,0
l_list = []
r_list = []
if a%c == 0:
    start_l = a//c
else:
    start_l = a//c+1
# print('left')
cn_l = b//c+1 - start_l
# for i in range(start_l, b//c+1):
#     l_list.append(c*i)
#     cn_l += 1
if a%d == 0:
    start_r = a//d
else:
    start_r = a//d+1
# print('right')
cn_r = b//d+1 - start_r
# for i in range(start_r, b//d+1):
#     r_list.append(d*i)
#     cn_r += 1
# print(cn_l, cn_r)
# for val in l_list:
#     if val in r_list:
#         cn_d +=1
def lcm(x, y):
    return (x * y) // gcd(x, y)
lcm = lcm(c,d)
if a%lcm == 0:
    start_d = a//lcm
else:
    start_d = a//lcm+1
cn_d = b//lcm+1 - start_d
n = b-a+1
print(n-(cn_l+cn_r-cn_d))
n, x = map(int, input().split())
m = []
sum = 0
for i in range(n):
    a = int(input())
    m.append(a)
    sum += a
m = sorted(m)
#print(m)
x -= sum

#cnt = n
#while x >= m[0]:
#    cnt += 1
#    x -= m[0]
cnt x // m[0]

print(cnt)


### FIXED CODE ###

n, x = map(int, input().split())
m = []
sum = 0
for i in range(n):
    a = int(input())
    m.append(a)
    sum += a
m = sorted(m)
#print(m)
x -= sum

cnt = n
while x >= m[0]:
    cnt += 1
    x -= m[0]

print(cnt)
import sys

s = sorted(input())
t = sorted(input())[::-1]
for i in range(len(s)):
    if s[i] < t[i]:
        print("Yes")
        sys.exit()
    elif s[i] > t[i]:
        print("No")
        sys.exit()
if len(t) > len(s):
    print("Yes")
else:
    print("No")

### FIXED CODE ###

import sys

s = sorted(input())
t = sorted(input())[::-1]
print("Yes" if s < t else "No")
N = int(input())
A = list(map(int,input().split()))
for x in range(N):
    A[x] -= (x+1)

sorted_A = sorted(A)

if N % 2 == 1:
    ans = sum(map(lambda x: abs(x-sorted_A[N//2+2]),A))
    for x in range(sorted_A[N//2],sorted_A[N//2+2]):
        y = sum(map(lambda z: abs(z -x),A))
        if ans > y :
            ans = y
else:
    ans = sum(map(lambda x: abs(x-sorted_A[N//2+1]),A))
    for x in range(sorted_A[N//2],sorted_A[N//2+1]):
        y = sum(map(lambda z: abs(z -x),A))
        if ans > y :
            ans = y
    
print(ans)

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
for x in range(N):
    A[x] -= (x+1)

sorted_A = sorted(A)

if len(A) == 1:
    ans = 0
else:
    ans = sum(map(lambda x: abs(x-sorted_A[N//2]),A))

print(ans)
N = int(input())
total = 0
tmp = 0
A = []
xy = []
for i in range(N):
  A.append(int(input())
  t = [list(map(int(input().split()))) for j in range(A[i])]
  xy.append(t)
for i in range(2**N):
  flag = 1
  i = format(i, '0{}b'.format(N))
  for k in range(N):
    if i[k] == '1':
      tmp += 1
      for l in range(A[k]):
        if int(i[xy[k][l][0]]) != xy[k][l][1]:
          flag = 0
          break
      else:
        continue
      break
  if flag == 1 and total < tmp:
    total = tmp
  tmp = 0
print(total)
          

### FIXED CODE ###

#標準入力受け取り
N = int(input())
shougen = []
A_lis = []
for _ in range(N):
    A = int(input())
    A_lis.append(A)
    minishougen = []
    for j in range(A):
        xy = list(map(int, input().split()))
        minishougen.append(xy)
    shougen.append(minishougen)

#ビットの配列作る
bit_lis = []
for i in range(2 ** N):
    mini_bit_lis = []
    for j in range(N):
        mini_bit_lis.append(i % 2)
        i = i // 2
    bit_lis.append(mini_bit_lis)
    
#ビットの配列について全探索を行う
ans = 0
for i in range(2 ** N):
    flag = 0
    for l in range(N):
        if bit_lis[i][l] == 1:
            for k in range(A_lis[l]): 
                if shougen[l][k][1] != bit_lis[i][shougen[l][k][0] - 1]:
                    flag = 1
                    break
        if flag == 1:
            break
    if flag == 0:
        tmp = sum(bit_lis[i])
        if tmp > ans :
            ans = tmp
print(ans)
s,k = [input() for i in range(2)]
for i in range(k):
    if int(s[i]) > 1:
        print(s[i])
        exit()
print(1)



### FIXED CODE ###

s,k = [input() for i in range(2)]
for i in range(int(k)):
    if int(s[i]) > 1:
        print(s[i])
        exit()
print(1)
print(int(input()//3)

### FIXED CODE ###

print(int(input())//3)
N = int(input("enter the number of cars: "))
i = int(input("enter the front of the train "))
if (1<=N and N<=100) or (1<=i and i<=N):
    i  = N - i +1
    print(i)


### FIXED CODE ###

t,i = map(int,input().split(" "))
j=t-i+1 
print(j)
S = input()
T = input()
ans = 0
for i in range(3):
    if S[i] == T[i]:
        ans += 1
print(ans

### FIXED CODE ###

S = input()
T = input()
ans = 0
for i in range(3):
    if S[i] == T[i]:
        ans += 1
print(ans)
from math import gcd
MOD = 10**9 + 7
n = int(input())
zero = 0
cnt = defaultdict()
for i in range(n):
    x, y = map(int, input().split())
    if x == 0 and y == 0:
        zero += 1
        continue
    g = gcd(x, y)
    x //= g
    y //= g
    if y < 0 or (y == 0 and x < 0):
        x *= -1
        y *= -1
    rot_90 = 1 if x <= 0 else 0
    if rot_90:
        x, y = y, -x
        cnt[(x, y)][rot_90] += 1

ans = 1
for s, t in cnt.values():
    now = 1
    now += (pow(2, s, MOD) - 1) % MOD
    now += (pow(2, t, MOD) - 1) % MOD
    ans *= now
ans -= 1
ans += zero
print(ans % MOD)

### FIXED CODE ###

from math import gcd
MOD = 10**9 + 7
n = int(input())
zero = 0
cnt = dict()
for i in range(n):
    x, y = map(int, input().split())
    if x == 0 and y == 0:
        zero += 1
        continue
    g = gcd(x, y)
    x //= g
    y //= g
    if y < 0 or (y == 0 and x < 0):
        x *= -1
        y *= -1
    rot_90 = 1 if x <= 0 else 0
    if rot_90:
        x, y = y, -x
    try:
        cnt[(x, y)][rot_90] += 1
    except KeyError:
        cnt[(x, y)] = [int(not rot_90), rot_90]

ans = 1
for s, t in cnt.values():
    now = 1
    now += (pow(2, s, MOD) - 1) % MOD
    now += (pow(2, t, MOD) - 1) % MOD
    ans *= now
ans -= 1
ans += zero
print(ans % MOD)
N = int(input())

import heapq 


def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i,i, cnt])

    if temp!=1:
        arr.append([temp,temp, 1])

    if arr==[]:
        arr.append([n,n,1])

    return arr

heap = factorization(N) 
# print(heap)
heapq.heapify(heap)
ans = 0

while(1):
    if N == 1:
        break
    sub,prime,cnt = heapq.heappop(heap)
    if N < sub:
        break
    if N % sub == 0:
        N = N // sub
        ans += 1
        if cnt > 1:
            cnt -= 1
            sub *= prime
            heapq.heappush(heap, [sub,prime,cnt])

print(ans)




### FIXED CODE ###

N = int(input())

import heapq 





def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i,i, cnt])

    if temp!=1:
        arr.append([temp,temp, 1])

    if arr==[]:
        arr.append([n,n,1])

    return arr

# for N in range(1,100000):
# N = 288
# print(N)

heap = factorization(N) 
# print(heap)
# print(heap)
heapq.heapify(heap)
ans = 0

while(heap):
    # print(heap)
    if N == 1:
        break
    sub,prime,cnt = heapq.heappop(heap)
    if N < sub:
        break
    if N % sub == 0:
        N = N // sub
        ans += 1
        if cnt > 0:
            cnt -= 1
            sub *= prime
            heapq.heappush(heap, [sub,prime,cnt])

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

to = [[] for _ in range(N)]
visited = [False] * N

def dfs(v):
    n_visited = sum([1 if v else 0 for v in visited])
    if n_visited == N:
        return 1 
    
    ret = 0
    for u in to[v]:
        if not visited[u]:
            visited[u] = True
            ret += dfs(u)
            visited[u] = False  # 最も深い点から帰ってくる道中に、始点を除く全ての点を未訪問にする => 他のパスを辿ることが可能になる

    return ret


for _ in range(N):
    a, b = map(int, input().split())
    to[a-1].append(b-1)
    to[b-1].append(a-1)

visited[0] = True
print(dfs(0))

### FIXED CODE ###

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

to = [[] for _ in range(N)]
visited = [False] * N

def dfs(v):
    if sum(visited) == N:
        return 1 
    
    ret = 0
    for u in to[v]:
        if not visited[u]:
            visited[u] = True
            ret += dfs(u)
            visited[u] = False  # 最も深い点から帰ってくる道中に、始点を除く全ての点を未訪問にする => 他のパスを辿ることが可能になる

    return ret


for _ in range(M):
    a, b = map(int, input().split())
    to[a-1].append(b-1)
    to[b-1].append(a-1)

visited[0] = True
print(dfs(0))
import numpy as np

N = int(input())
# P = np.array(input().split(' '), dtype = int)
P = np.array(list(map(int, input().split(' '))))

# print(N - sum([np.any(P[:i+1] < P[i]) for i in range(N)]))
for i in range(N):
    N -= np.any((P < P.reshape(-1,1))[i][:i+1])
print(N)


### FIXED CODE ###

N = int(input())
# P = np.array(input().split(' '), dtype = int)
P = list(map(int, input().split(' ')))

p_min = P[0]
ans = 0
for p in P:
    if p <= p_min:
        p_min = p
        ans += 1
print(ans)
ans_min = x * a + y * b
for i in range(100000):
    ans = i * 2 * c + max(0, x - i) * a + max(0, y - i) * b
    if ans < ans_min:
        ans_min = ans
print(ans)

### FIXED CODE ###

a, b, c, x, y = map(int, input().split())
 
ans_min = x * a + y * b
for i in range(100001):
    ans = i * 2 * c + max(0, x - i) * a + max(0, y - i) * b
    if ans < ans_min:
        ans_min = ans
 
print(ans_min)
d,t,s =int(input()),(input()),int(input())
t1 = d/s
if t1<= t:
  print("Yes")
else:
  print("No")


### FIXED CODE ###

d=input()
arr = [int(i) for i in d.split()]

t1 = arr[0]/arr[-1]
if t1<= arr[1]:
  print("Yes")
else:
  print("No")
H, N = map(int, input().split())
total_A = sum(list(map(int, input.split())))

if H <= total_A:
    print('Yes')
else:
    print('No')


### FIXED CODE ###



H, N = map(int, input().split())
total_A = sum(list(map(int, input().split())))

if H <= total_A:
    print('Yes')
else:
    print('No')
N=int(input())
a=0
d=1
while d<=N:
  a+=d
  d*=2
print(ans)

### FIXED CODE ###

N=int(input())
a=0
d=1
while d<=N:
  a+=d
  d*=2
print(a)
import bisect

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

L.sort()

buff = []
ll = []


for i in range(N):
    l_b = []
    for j in range(i+1, N):
        l_b.append(L[i]+L[j])
        ll.append(L[i]+L[j])
    if i != N-1:
        buff.append(l_b)
# buff.sort()
# print(L)
# print(buff)

ans = 0
_len = len(buff)

for i in range(_len):
    for j in range(len(buff[i])):
        index = bisect.bisect_left(L[i+j+1+1:], buff[i][j])
        # print(L[i+j+1+1:])
        # print(index, buff[i][j])
        ans += index
print(ans)


# for i in range(N):
#     index = bisect.bisect_left(buff, L[i])
#     print(index)
#     ans += index
# print(ans)


### FIXED CODE ###

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

if A - (B*2) > 0:
    print(A - (B*2))
else:
    print(0)
import sys
#sys.setrecursionlimit(10**9)
input = sys.stdin.readline
n, m = map(int, input().split())
d = {}
for i in range(n):
    d[i] = 0

for i in range(n):
    a, b = map(int, input().split())
    a, b = a-1, b-1
    d[a] += 1
    d[b] += 1

for v in d.values():
    if v%2 != 0:
        print('NO')
        exit()
else:
    print('YES')

### FIXED CODE ###

import sys
#sys.setrecursionlimit(10**9)
input = sys.stdin.readline
n, m = map(int, input().split())
d = {}
for i in range(n):
    d[i] = 0

for i in range(m):
    a, b = map(int, input().split())
    a, b = a-1, b-1
    d[a] += 1
    d[b] += 1

for v in d.values():
    if v%2 != 0:
        print('NO')
        exit()
else:
    print('YES')
N = int(input())
L = list(map(int, input().split()))

L.sort
if sum(L[:-1]) > L[-1]
    ans = "Yes"
else: ans = "No"

print(ans)

### FIXED CODE ###

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

L.sort()

if sum(L[:-1]) > L[-1]:
    ans = "Yes"
else: ans = "No"

print(ans)
#from fractions import gcd
#from math import gcd
import numpy as np
#import math
#import sys
#input = sys.stdin.readline
mod = 10**9+7


def obtain_ps(n):
    ps = {}
    # while(n>1):
    n_input = n

    for i_tmp in range(2, int(n_input**0.5)+1):
        if not n % i_tmp == 0:
            continue
        i_tmp2 = n//i_tmp
        for i in [i_tmp, i_tmp2]:
            i_primary = True
            for j in range(2, int(i**0.5)+1):
                if i % j == 0:
                    i_primary = False
                    break
            if not i_primary:
                continue
            count = 1
            r = i
            while(not n % r):
                count += 1
                r *= i
            count -= 1
            ps[i] = count
            n = n/(i**count)
            if n == 1:
                break
    if n == n_input:
        ps[n] = 1
    return ps


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

ps = {}
ps_s = []
for s in A:
    ps_tmp = obtain_ps(s)
    ps_s.append(ps_tmp)
    for k, v in ps_tmp.items():
        if k in ps.keys():
            ps[k] = max(v, ps_tmp[k])
        else:
            ps[k] = v

ans = 0
for ps_tmp in ps_s:
    plus = 1
    for k, v in ps.items():
        if k in ps_tmp.keys():
            plus *= k**(v-ps_tmp[k]) % mod
        else:
            plus *= k**v % mod

    ans += plus % mod
#lcm=np.product([k**v for k,v in ps.items()])

#ans = np.sum([lcm // s %mod for s in A]) % mod

print(int(ans % mod))

### FIXED CODE ###

from fractions import gcd
#from math import gcd
import numpy as np
import sys
input = sys.stdin.readline
mod = 10**9+7

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

lcm = 1
for s in A:
    lcm = s*lcm//gcd(lcm, s)

ans = lcm*sum([pow(s, mod-2, mod) for s in A]) % mod
#ans = sum([lcm//s % mod for s in A]) % mod

print(int(ans%mod))
n=int(input())
l=list(map(int,input().split()))
tl=[l[0]]
for i in range(1,n):
    if l[i]!=l[i-1]:
        tl.append(l[i])


a=[]
ma=False

for i in range(len(tl)):
    if i==0:
        if tl[i]>tl[i+1]:
            ma=True
            a.append(tl[i])
        else:
            ma=False
            a.append(tl[i])
    elif i==len(tl)-1:
        if tl[i]>tl[i-1]:
            a.append(tl[i])
        else:
            a.append(tl[i])
    else:
        if tl[i-1]<tl[i] and tl[i+1]<tl[i]:
            a.append(tl[i])
        elif tl[i-1]>tl[i] and tl[i+1]>tl[i]:
            a.append(tl[i])

if ma:
    a.pop(0)


num=0
ans=1000

for i in range(0,len(a)-1,2):
    
    thing1=(ans//(a[i]))*a[i+1]
    thing2=num*a[i+1]
    if thing1>thing2:
        ans=thing1+ans%a[i]
        num=0
        
    elif thing2>thing1:
        ans=thing2

print(ans)
            
            
        

    


### FIXED CODE ###

n=int(input())
l=list(map(int,input().split()))
tl=[l[0]]
for i in range(1,n):
    if l[i]!=l[i-1]:
        tl.append(l[i])


a=[]
ma=False

for i in range(len(tl)):
    if len(tl)==1:
        break
    if i==0:
        if tl[i]>tl[i+1]:
            ma=True
            a.append(tl[i])
        else:
            ma=False
            a.append(tl[i])
    elif i==len(tl)-1:
        if tl[i]>tl[i-1]:
            a.append(tl[i])
        else:
            a.append(tl[i])
    else:
        if tl[i-1]<tl[i] and tl[i+1]<tl[i]:
            a.append(tl[i])
        elif tl[i-1]>tl[i] and tl[i+1]>tl[i]:
            a.append(tl[i])

if ma:
    a.pop(0)


num=0
ans=1000

for i in range(0,len(a)-1,2):
    
    thing1=(ans//(a[i]))*a[i+1]
    thing2=num*a[i+1]
    if thing1>thing2:
        ans=thing1+ans%a[i]
        num=0
        
    elif thing2>thing1:
        ans=thing2

print(ans)
a=1
while True:
  x=raw_input()
  if x!=0:
    
    print('Case '+str(a)+':'+x)
    a+=1
  elif x==0:
    break

### FIXED CODE ###

a=1
while True:
  x=raw_input()
  if x!='0':
    
    print('Case '+str(a)+': '+x)
    a+=1
  elif x=='0':
    break
# -*- coding: utf-8 -*-
"""
Created on Mon May 27 22:13:19 2019

@author: Yamazaki Kenichi
"""

N, M = map(int,input().split())
ks = [list(map(int,input().split())) for i in range(M)]
p = list(map(int,input().split()))

S = [0 for i in range(M)]
for i in range(M):
    for j in range(1,ks[i][0]+1):
        S[i] += 2**(ks[i][j]-1)

ans = 0
for bit in range(1<<N):
    now = [0 for i in range(M)]
    for i in range(N):
        if bit & 1<<i:
            for j in range(M):
                now[j] += S[j]//(1<<i)
    flg = True
    for j in range(M):
        if now[j]%2 != p[j]:
            flg = False
    ans += flg
print(ans)


### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
Created on Sun May 26 20:56:05 2019

@author: Yamazaki Kenichi
"""
import heapq

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

def a(K):
    if K > N:
        return N
    else:
        return K

ans = 0
for i in range(K):
    for j in range(a(K-i)+1):
        tmp = 0
        minus = [0]
        for k in range(a(K-i)):
            tmp += V[k-j]
            heapq.heappush(minus,V[k-j])
#            print(tmp,minus)
        for k2 in range(i):
            if minus[0] < 0:
                tmp += (-heapq.heappop(minus))
            else:
                break
#        print(ans,tmp,i,j,k)
        ans = max(ans,tmp)
    
print(ans)
#!/usr/bin/env python
# -*- coding: utf-8 -*-
n=int(input())
a=[int(x) for x in input().split()]
mod=10**9+7
b=[]
lcm=1
from math import gcd
for ai in a:
    lcm=ai*lcm//gcd(ai,lcm)
ans=0
for ai in a:
    ans+=lcm//ai
    ans%=mod
print(ans)

### FIXED CODE ###

#!/usr/bin/env python
# -*- coding: utf-8 -*-
n=int(input())
a=[int(x) for x in input().split()]
mod=10**9+7
lcm=1
from fractions import gcd
for ai in a:
    lcm=ai*lcm//gcd(ai,lcm)
ans=0
for ai in a:
    ans+=lcm//ai
print(ans%mod)
n, m = map(int, input().split())
edges = [set() for _ in range(n)]
for _ in range(m):
    a, b, c = map(int, input().split())
    edges[a - 1].add((b - 1, c))

NINF = float('-inf')
dists = [NINF for _ in range(n)]
dists[0] = 0


def trace(v, updated):
    updated[v] = True
    for b, c in edges[v]:
        if not updated[b]:
            trace(b, updated)


def bellman_ford():
    for i in range(n - 1):
        updated = False
        for j in range(n):
            dj = dists[j]
            if dj == NINF:
                continue
            for b, c in edges[j]:
                if dists[b] >= dj + c:
                    continue
                dists[b] = dj + c
                updated = True
        if not updated:
            return dists[-1]

    n_updated = [False] * n
    for j in range(n):
        if n_updated[j]:
            continue
        dj = dists[j]
        if dj == NINF:
            continue
        for b, c in edges[j]:
            if dists[b] < dj + c:
                trace(b, n_updated)

    return 'inf' if n_updated[-1] else dists[-1]


print(bellman_ford())


### FIXED CODE ###

import sys
sys.setrecursionlimit(10000)

n, m = map(int, input().split())
edges = [set() for _ in range(n)]
for _ in range(m):
    a, b, c = map(int, input().split())
    edges[a - 1].add((b - 1, c))

NINF = float('-inf')
dists = [NINF for _ in range(n)]
dists[0] = 0


def trace(v, updated):
    updated[v] = True
    for b, c in edges[v]:
        if not updated[b]:
            trace(b, updated)


def bellman_ford():
    for i in range(n - 1):
        updated = False
        for j in range(n):
            dj = dists[j]
            if dj == NINF:
                continue
            for b, c in edges[j]:
                if dists[b] >= dj + c:
                    continue
                dists[b] = dj + c
                updated = True
        if not updated:
            return dists[-1]

    n_updated = [False] * n
    for j in range(n):
        if n_updated[j]:
            continue
        dj = dists[j]
        if dj == NINF:
            continue
        for b, c in edges[j]:
            if dists[b] < dj + c:
                trace(b, n_updated)

    return 'inf' if n_updated[-1] else dists[-1]


print(bellman_ford())
n, m = map(int, input().split())
p = [int(i) for i in input().split()]
graph = [[] for _ in range(n)]
group = [0]*n
ans = 0
for _ in range(m):
    x, y = map(int, input().split())
    graph[x].append(y)
    graph[y].append(x)
for i, num in enumerate(p):
    space = [i]
    for point in space:
        if group[point]:
            continue
        group[point] = i+1
        space.extend(graph[point])
    ans += (group[num] == group[i])
print(ans)

### FIXED CODE ###

N, M = map(int, input().split())
# p = [int(i) for i in input().split()]
p = map(int,input().split())
# graph = [[]]*(N+1)
graph = [[] for _ in range(N+1)]
group = [0]*(N+1)
ans = 0
for _ in range(M):
    x, y = map(int, input().split())
    graph[x].append(y)
    graph[y].append(x)
for i, num in enumerate(p, 1):
    space = [i]
    for point in space:
        if group[point]:
            continue
        group[point] = i
        space.extend(graph[point])
    ans += (group[num] == group[i])
print(ans)
S,T = [x for x in input().split()]
A,B = [int(x) for x in input().split()]
U = input()

if S == U:
  A -= 1
elif T == U:
  B -= 1

print(f"{A} {B}")

### FIXED CODE ###

S,T = [x for x in input().split()]
A,B = [int(y) for y in input().split()]
U = input()

if S == U:
  A -= 1
elif T == U:
  B -= 1

print(A,end=" ")
print(B)