Harryxun/stf_run huggingface dataset:
alice = 0
bob = 0
n = int(input())
a = sorted(list(map(int, input().split(' ')))).reverse()

for i in a[::2]: alice += i
for i in a[1::2]: bob += i
print(alice - bob)

### FIXED CODE ###

alice = 0
bob = 0
n = int(input())
a = list(map(int, input().split(' ')))
asrt = sorted(a, reverse = True)

for i in asrt[::2]: alice += i
for i in asrt[1::2]: bob += i
print(alice - bob)
n = int(input())
p = tuple(map(int,input().split()))
q = tuple(map(int,input().split()))

l = list(range(1,n+1))
dic = {}

for i,j in enumerate(itertools.permutations(l)):
    dic[j] = i+1
print(abs(dic[p]-dic[q]))

### FIXED CODE ###

import itertools
 
n = int(input())
p = tuple(map(int,input().split()))
q = tuple(map(int,input().split()))

l = list(range(1,n+1))
dic = {}

for i,j in enumerate(itertools.permutations(l)):
    dic[j] = i+1
print(abs(dic[p]-dic[q]))
import sys
N = int(input())
A = [int(a) for a in sys.stdin.readline().split()]

dic = {}
for a in A:
  dic[a] = dic.get(a,0) + 1

evenodd = [0,0]
for k in dic:
  evenodd[dic[k]%2] += 1
if evenodd[0]%2==0:
  return len(dic)
else:
  return len(dic)-1
  






### FIXED CODE ###

import sys
N = int(input())
A = [int(a) for a in sys.stdin.readline().split()]

dic = {}
for a in A:
  dic[a] = dic.get(a,0) + 1

evenodd = [0,0]
for k in dic:
  evenodd[dic[k]%2] += 1
if evenodd[0]%2==0:
  print(len(dic))
else:
  print(len(dic)-1)
a=input()
b='Sunny'
c='Cloudy'
d='Rainy'
if a=b:
 print(c)
elif a=c:
 print(d)
elif a=d:
 print(b)


### FIXED CODE ###

a = input()
b = 'Sunny'
c = 'Cloudy'
d = 'Rainy'
if a == b:
 print(c)
if a == c:
 print(d)
if a == d:
 print(b)
N = int(input())
l = list()
al = list()
bl = list()
 
for n in range(0,N):
    a = input()
　 l.append(a)
    al.append(a[:1])
    bl.append(a[-1:])
 
l_unq = list(set(l))
if len(l) == len(l_unq):
    for i in range(0,N-1):
        if al[i+1] != bl[i]:
          print("No")
          break
     print("Yes")
else:
    print("No")

### FIXED CODE ###

N = int(input())
l = list()

for n in range(N):
    a = input()
    l.append(a)

l_uniq = list(set(l))

if len(l) == len(l_uniq):
    for i in range(0, N-1):
        if l[i+1][0] != l[i][-1]:
            print("No")
            break
    else:
        print("Yes")
else:
    print("No")
import numpy as np
 
MOD = 10**9+7
 
D,T,E = int(input().split())
n= int(D)
arr = np.zeros((n+1,n+1),dtype=np.int16)
for i in range(3,n+1):
    arr[0,i] = 1

### FIXED CODE ###

D,T,S = [int(i) for i in input().split()]
out = 'Yes' if D <= T * S else 'No'
print(out)
N, M = map(int, input().split())
A = [int(input()) for _ in range(M)]

B = [-1] + A + [N + 1]
B = [B[i + 1] - B[i] - 2 for i in range(M + 1)]

total = max(B)
dp = [0] * (total + 1)
dp[0] = 1
dp[1] = 1

for i in range(total - 1):
    dp[i + 2] = (dp[i + 1] + dp[i]) #% (10 ** 9 + 7)
        
ans = 1
for i in range(M + 1):
    ans *= dp[B[i]]
    ans %= 10 ** 9 + 7
print(ans if -1 not in B[1:] else 0)

### FIXED CODE ###

N, M = map(int, input().split())
A = [int(input()) for _ in range(M)]

B = [-1] + A + [N + 1]
B = [B[i + 1] - B[i] - 2 for i in range(M + 1)]

total = max(B)
dp = [1, 1] + [0] * (total - 1)
for i in range(total - 1):
    dp[i + 2] = (dp[i + 1] + dp[i]) % (10 ** 9 + 7)
        
ans = 1
for i in range(M + 1):
    ans *= dp[B[i]]
    ans %= 10 ** 9 + 7
print(ans if -1 not in B[1:] else 0)
while 1:
    m,n=map(int,input().split())
    if m==0:break
    a,i,c=list(range(1,m+1)),0,0
    while i<n:
        i+=1
        b,f=input(),0
        if m<2:continue
        if i%15==0:
            if b!='FizzBuzz':
                del a[c]
                f=1
        elif i%5==0:
            if b!='Buzz':
                del a[c]
                f=1
        elif i%3==0:
            if b!='Fizz':
                del a[c]
                f=1
        elif b!=str(i):
            del a[c]
            f=1
        if f:
            m-=1
            c%m
        else:c=(c+1)%m
    print(*a)

### FIXED CODE ###

while 1:
    m,n=map(int,input().split())
    if m==0:break
    a,i,c=list(range(1,m+1)),0,0
    while i<n:
        i+=1
        b,f=input(),0
        if m<2:continue
        if i%15==0:
            if b!='FizzBuzz':
                del a[c]
                f=1
        elif i%5==0:
            if b!='Buzz':
                del a[c]
                f=1
        elif i%3==0:
            if b!='Fizz':
                del a[c]
                f=1
        elif b!=str(i):
            del a[c]
            f=1
        if f:m-=1
        else:c+=1
        c%=m
    print(*a)
n = input().split()
N = int(n[0])
K = int(n[1])
s = [list(map(int, input().split())) for i in range(2*K+1)] 
b = list(range(N))
for l in b:
    for i in range(K):
        di = s[2*i]
        ai = s[2*i+1]
        for k in ai:
            if k == l:
                b.remove(l)
                ai.remove(l)
print(len(b))

### FIXED CODE ###

N, K = map(int, input().split())
d = []
A = []
s = [1] * N
for k in range(K):
  d.append(int(input()))
  A.append([int(i) for i in input().split()])
  
for k in range(K):
  for n in range(1, N+1):
    if n in A[k]:
      if s[n-1] == 1:
        s[n-1] = 0
print(sum(s))
N, A, B, C = map(int, input().split())
l = [int(input()) for i in range(N)]
INF = 10 ** 9

def dfs(cur, a, b, c):
    if cur == N:
        return abs(a-A) + abs(b-B) + abs(C-C) - 30 if min(a, b, c) > 0 else INF
    ret0 = dfs(cur+1, a, b, c)
    ret1 = dfs(cur+1, a+l[cur], b, c) + 10
    ret2 = dfs(cur+1, a, b+l[cur], c) + 10
    ret3 = dfs(cur+1, a, b, c+l[cur]) + 10
    return min(rest0, ret1, ret2, ret3)

print(dfs(0, 0, 0, 0))

### FIXED CODE ###

N, A, B, C = map(int, input().split())
l = [int(input()) for i in range(N)]
INF = 10 ** 9

def dfs(cur, a, b, c):
    if cur == N:
        return abs(a-A) + abs(b-B) + abs(c-C) - 30 if min(a, b, c) > 0 else INF
    ret0 = dfs(cur+1, a, b, c)
    ret1 = dfs(cur+1, a+l[cur], b, c) + 10
    ret2 = dfs(cur+1, a, b+l[cur], c) + 10
    ret3 = dfs(cur+1, a, b, c+l[cur]) + 10
    return min(ret0, ret1, ret2, ret3)

print(dfs(0, 0, 0, 0))
def main_C1():

  N = int(input())
  a = [[int(item) for item in line.split()] for line in input()]
  
  dp = [[0, 0, 0] for i in range(N+1)]

  for i in range(N):
    for j in range(3):
      for k in range(3):
        if j == k:
          continue
        dp[i+1][k] = max(dp[i+1][k], dp[i][j] + a[i][k])
  
  print(max(dp[-1]))

if __name__ == "__main__":
  main_C1()
  # print(list(input_gen()))

### FIXED CODE ###

def main_C1():

  N = int(input())
  a = [[int(item) for item in input().split()] for i in range(N)]
  
  dp = [[0, 0, 0] for i in range(N+1)]

  for i in range(N):
    for j in range(3):
      for k in range(3):
        if j == k:
          continue
        dp[i+1][k] = max(dp[i+1][k], dp[i][j] + a[i][k])
  
  print(max(dp[-1]))

if __name__ == "__main__":
  main_C1()
  # print(list(input_gen()))
import bisect
n=int(input())
a=sorted(list(map(int,input().split())))
b=sorted(list(map(int,input().split())))
c=sorted(list(map(int,input().split())))
ab={} #ab[i]:上部にi個目を選んだ時、中部に選べるもののうち最小のインデックス。選べないならnになる
l=bisect.bisect_right(b,a[0])
ab[0]=l
for i in range(1,n):
  if a[i]<b[ab[i-1]]:
    ab[i]=ab[i-1]
  else:
    j=ab[i-1]+1
    while n>j and a[i]>=b[j]:
      j+=1
    ab[i]=j
bc={} 
l=bisect.bisect_right(c,b[0])
bc[0]=l
for i in range(1,n):
  if b[i]<c[bc[i-1]]:
    bc[i]=bc[i-1]
  else:
    j=bc[i-1]+1
    while n>j and b[i]>=c[j]:
      j+=1
    bc[i]=j
ans=0
for i in range(n):
  for j in range(ab[i],n):
    ans+=n-bc[j]


### FIXED CODE ###

def main(n,a,b,c):
  import bisect
  ans=0
  for i in range(n):
    na=bisect.bisect_left(a,b[i])
    nc=n-bisect.bisect_right(c,b[i])
    ans+=na*nc
  print(ans)
if __name__=='__main__':
  n=int(input())
  a=sorted(list(map(int,input().split())))
  b=sorted(list(map(int,input().split())))
  c=sorted(list(map(int,input().split())))
  main(n,a,b,c)
l = map(int,input().split())
l.sort()
print(10*l[0] + l[1] + l[2])

### FIXED CODE ###

l = list(map(int,input().split()))
l.sort()
print(10*l[2] + l[1] + l[0])
n=int(input())
str(n)
array = list(map(int,s))
if array%9==0:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

n=int(input())
s=str(n)
array = list(map(int,s))
if sum(array)%9==0:
    print("Yes")
else:
    print("No")
nm = input()
nm = nm.split()
n = int(nm[0])
m = int(nm[1])
nums = input()
nums = nums.split()
nums2 = []
for i in nums:
  nums2.append(int(i))
nums3 = []
i = 1
while i<len(nums2):
  nums3.append(nums2[i]-nums2[i-1])
  i+=1
for i in range(n-1):
  nums3.remove(max(nums3))
print(sum(nums3))

### FIXED CODE ###

nm = input()
nm = nm.split()
n = int(nm[0])
m = int(nm[1])
nums = input()
nums = nums.split()
nums2 = []
for i in nums:
  nums2.append(int(i))
nums2.sort()
nums3 = []
i = 1
while i<len(nums2):
  nums3.append(nums2[i]-nums2[i-1])
  i+=1
nums3.sort()
nums3 = nums3[:len(nums3)-n+1]
if(n>=m):
  print(0)
else:
  print(sum(nums3))
a, b = map(int, input().rstrip().split())

if a * b % 2 == 0:
  print("Even")
eles:
  print("Odd")

### FIXED CODE ###

a, b = map(int, input().rstrip().split())

if a * b % 2 == 0:
  print("Even")
else:
  print("Odd")
n=input()
sn=""
for i in range(len(n)):
    sn+=str(n[i])
if int(n)%sm==0:
    print("Yes")
else:
    print("No")


### FIXED CODE ###

n=input()
sn=0
for i in range(len(n)):
    sn+=int(n[i])
if int(n)%sn==0:
    print("Yes")
else:
    print("No")
n, m, k=map(int, input().split())
a=list(map(int, input().split()))+[10**10]*(10**10)
b=list(map(int, input().split()))+[10**10]*(10**10)

loop=max(n, m)
i=0
j=0
T=0
ans=0

for t in range(2*loop):
    if a[i]>=b[j]:
        T+=b[j]
        if T<=k:
            ans+=1
            j+=1
        else:
            print(ans)
            exit()
    elif b[j]>a[i]:
        T+=a[i]
        if T<=k:
            ans+=1
            i+=1
        else:
            print(ans)
            exit()
    
    elif i==n-1:
        T+=b[j]
        if T<=k:
            ans+=1
            j+=1
        else:
            print(ans)
            exit()
    
    elif j==m-1:
        T+=a[i]
        if T<=k:
            ans+=1
            i+=1
        else:
            print(ans)
            exit()

### FIXED CODE ###

n, m, k=map(int, input().split())
A=list(map(int, input().split()))
B=list(map(int, input().split()))

a=[0]
b=[0]

for i in range(n):
    a.append(a[i]+A[i])

for i in range(m):
    b.append(b[i]+B[i])

ans, j=0, m
for i in range(0, n+1):
    if a[i]>k:
        break
    else:
        while a[i]+b[j]>k:
            j-=1
        
    ans=max(ans, i+j)


print(ans)
a

### FIXED CODE ###

a,b=map(int,input().split())
if (a+b )%2==1:
  print(int((a+b+1)/2))
else:
  print(int((a+b)/2))
import sys, os, re
from pprint import pprint
from math import sin, cos, sqrt, radians

n, m = list(map(int, sys.stdin.readline().strip().split()))
g = [[] for x in range(n)]

for i in range(n):
    x, y = list(map(int, sys.stdin.readline().strip().split()))
    x -= 1
    y -= 1

ans = {0: -1}

while len(ans) < n:
    flag = False
    for k, v in ans.items():
        for node in g[k]:
            if node not in ans:
                ans[node] = k
                flag = True
    if flag == False:
        break

print("Yes")
for i in range(1, n):
    print(ans[i]+1)
    

### FIXED CODE ###


import sys, os, re
from pprint import pprint
from math import sin, cos, sqrt, radians

n, m = list(map(int, sys.stdin.readline().strip().split()))
g = [[] for x in range(n)]

for i in range(m):
    x, y = map(int, sys.stdin.readline().strip().split())
    x -= 1
    y -= 1
    g[x].append(y)
    g[y].append(x)

if [] in g:
    print("No")
    exit(0)

ans = {0: -1}
tmp = [0]

while len(ans) < n:
    tmp_next = []
    for k in tmp:
        for node in g[k]:
            if node not in ans:
                ans[node] = k
                tmp_next.append(node) 
                flag = True

        tmp = tmp_next
        if flag == False:
            break

    """
    flag = False    
    for k, v in list(ans.items()):
        for node in g[k]:
            if node not in ans:
                ans[node] = k
                flag = True
    if flag == False:
        break
    """

print("Yes")
for i in range(1, n):
    print(ans[i]+1)
from math import gcd
n,x=map(int,input().split())
l = [abs(int(i) - x) for i in input().split()]
ans = l[0]
for i in l:
    ans = gcd(ans,i)
print(ans)

### FIXED CODE ###

import functools
def gcd( a, b ):
    while b != 0:
        a, b = b,a%b
    return a
n,x=map(int,input().split())
l = [abs(int(i) - x) for i in input().split()]
print(functools.reduce(gcd,l))
print(int(input()) * int(input()))

### FIXED CODE ###

a, b = map(int, input().split())
print(a*b)
from itertools import accumulate
n,x = map(int, input().split())
a = [0, *map(int, input().split())]
print(len([i for i in accumulate(a) if i < x+1]))

### FIXED CODE ###

from itertools import accumulate
n,x = map(int, input().split())
a = [0] + list(map(int, input().split()))
print(len([i for i in accumulate(a) if i < x+1]))
N = int(input())
a = []
for i in range(N):
    a.append(map(int, input())

int(N)    

for i in range(N):
    v = a[i]
    j = i-1
    while j>=0 and a[j]>v:
        a[j+1] = a[j]
        j = j-1
        a[j+1] = v
    print(a) 


### FIXED CODE ###

N = int(input())
a = input().split()
b = [int(n) for n in a]


for i in range(N):
    v = b[i]
    j = i-1
    while j>=0 and b[j]>v:
        b[j+1] = b[j]
        j = j-1
        b[j+1] = v
    print(" ".join([str(n) for n in b]))
from scipy import ndimage
import numpy as np
import sys
 
H, W = map(int, input().split())
 
A_array = np.array(
    [[0 if s == "#" else 1 for s in input()[:-1]] for i in range(H)])
# print(A_array)
 
 
# print(A_array)
b = ndimage.morphology.distance_transform_cdt(
    A_array, metric="taxicab")
print(np.max(b))

### FIXED CODE ###

from scipy import ndimage
import numpy as np

 
H, W = map(int, input().split())
 
A_array = np.array(
    [[0 if s == "#" else 1 for s in input()] for i in range(H)])
# print(A_array)
 
# print(A_array)
b = ndimage.morphology.distance_transform_cdt(
    A_array, metric="taxicab")
print(np.max(b))
n,a,b,ax,bx=int(input()),list(map(int,input().split()))+[0],list(map(int,input().split()))+[0],0,0
na,nb=a,b
for i in range(n):
	a[n]^=a[i]
	b[n]^=b[i]
a,b=sorted(a),sorted(b)
if sum([a[i]!=b[i] for i in range(n+1)]):
	print("-1")
	exit()
f=dict()
def find(x):
	if f[x]==x:
		return x
	else:
		f[x]=find(f[x])
		return f[x]
ans=0
for i in range(n):
	if na[i]!=nb[i]:
		f[na[i]]=na[i]
f[a[n]]=a[n]
for i in range(n):
	if na[i]!=nb[i]:
		ans+=1
		f[find(nb[i])]=find(na[i])
for i,j in f:
	if i==j:
		ans+=1
print(ans-1)

### FIXED CODE ###

n,a,b=int(input()),list(map(int,input().split()))+[0],list(map(int,input().split()))+[0]
for i in range(n):
	a[n]^=a[i]
	b[n]^=b[i]
na,nb=sorted(a),sorted(b)
if na!=nb:
	print("-1")
	exit()
f=dict()
def find(x):
	if f[x]==x:
		return x
	else:
		f[x]=find(f[x])
		return f[x]
ans=0
for i in range(n):
	if a[i]!=b[i]:
		f[a[i]]=a[i]
f[a[n]]=a[n]
for i in range(n):
	if a[i]!=b[i]:
		ans+=1
		f[find(b[i])]=find(a[i])
for i in f:
	if i==f[i]:
		ans+=1
print(ans-1)
# D - Various Sushi
import sys
from collections import defaultdict
import heapq
readline = sys.stdin.readline

dd = defaultdict(list)
N, K = map(int, readline().split())
for i in range(N):
    t, d = map(int, readline().split())
    heapq.heappush(dd[t], d*-1)

dd = list(dd.values())
dd.sort()

ans = 0
fix = 0
var = []
for i in range(len(dd)):
    fix += heapq.heappop(dd[i]) * -1
    while len(dd[i]) > 0:
        tmp = heapq.heappop(dd[i]) * -1
        heapq.heappush(var, tmp)
    while len(var) > K-i-1:
        heapq.heappop(var)
    if len(var) == K-i-1:
        ans = max(ans , fix+sum(var) + (i+1)**2)

print(ans)

### FIXED CODE ###

# D - Various Sushi
import sys
from collections import defaultdict
import heapq

readline = sys.stdin.readline

dd = defaultdict(list)
N, K = map(int, readline().split())
for i in range(N):
    t, d = map(int, readline().split())
    heapq.heappush(dd[t], d*-1)

dd = list(dd.values())
dd.sort()

ans = 0
fix = 0
var = []
len_var = 0
sum_var = 0
tmp_max = 0

for i in range(min(K, len(dd))):
    fix += heapq.heappop(dd[i]) * -1
    for _ in range(len(dd[i])):
        tmp = heapq.heappop(dd[i]) * -1
        heapq.heappush(var, tmp)
        len_var += 1
        sum_var += tmp
    while len_var > K-(i+1) and len_var > 0:
        del_var = heapq.heappop(var)
        len_var -= 1
        sum_var -= del_var
    if len_var == K-(i+1):
        ans = max(ans , fix+sum_var + (i+1)**2)

print(ans)
import collections

n, p = map(int, input().split())
res = []
x = p
y = 2
while y*y <= x:
    while x % y == 0:
        res.append(y)
        x //= y
    y += 1
if x > 1:
    res.append(x)

res = collections.Counter(res)
ans = 1
for d in res.items():
    if d[1] >= n:
        ans *= d[0]**d[1]//n
print(ans)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
cnt, nega, posi = 0, 0, []
for x, y in zip(a, b):
    if x < y:
        nega += y - x
        cnt += 1
    else:
        posi.append(x - y)
if nega > 0:
    posi.sort(reverse=True)
    for i, x in enumerate(posi):
        nega -= x
        if nega <= 0:
            cnt += i + 1
            break
    else:
        cnt = -1
print(cnt)
params = input().split(' ')
n = eval(params[1])
 
acfoundfor = []
 
penalties = 0
points = 0
 
for i in range(n):
    submission = input().split(' ')
    p = eval(submission[0])
    status = submission[1]
    
    if p in acfoundfor:
        continue
 
    if status == 'AC':
        points += 1
        acfoundfor.append(p)
    else:
        penalties += 1
        
print(points, penalties)

### FIXED CODE ###

x = input()
y = ord(x)
y += 1
x = chr(y)
print(x)
N = int(input())
total = 0
for i in range(1,N+1)
    if i%3 != 0 and i%5 ! =0:
        total += i
print(total)

### FIXED CODE ###

N = int(input())
total = 0
for i in range(1, N+1):
    if (i % 3) != 0 and (i % 5) != 0:
        total = total+i
print(total)
from enum import Enum
from queue import Queue
import collections

import sys
import math

BIG_NUM = 2000000000
MOD = 1000000007
EPS = 0.000000001

N,K = map(int,input().split())
dp=[[0 for i in range(N)] for j in range(N)]

for i in range(N):
    dp[i][0] = 1
    for j in range(1,N):
        dp[i][j] = dp[i-1][j-1] + dp[i-1][j]

for i in range(1,K+1):
    print(dp[N-K+1][i]*dp[K-1][i-1]%MOD)


### FIXED CODE ###

BIG_NUM = 2000000000
MOD = 1000000007
EPS = 0.000000001

import math

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

def combination_fuc(n,r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
#dp=[[0 for i in range(N)] for j in range(N)]
#for i in range(N):
#    dp[i][0] = 1
#    dp[i][i] = 1
#for i in range(2,N):
#    for j in range(1,i):
#        dp[i][j] = dp[i-1][j-1] + dp[i-1][j]
#for i in range(1,K+1):
#    tmp=dp[N-K+1][i]*dp[K-1][i-1]
#    if tmp > MOD:
#        print(tmp%MOD)
#    else:
#        print(tmp)

for i in range(1,K+1):
    if N-K+1 >= i:
        print((combination_fuc(N-K+1,i)*combination_fuc(K-1,i-1))%MOD)
    else:
        print(0)
N,M = map(int,input().split())
h = [list(map(int, input().split()))for i in range(M)]
for i in range(M):
    h[i].append(i)
h = sorted(h,key=lambda h:(h[0],h[1]))
k = 0
p = h[0][0]
for i in range(M):
    if h[i][0] == p:
        h[i].append(str(p).zfill(6)+str(k+1).zfill(6))
        k+=1
    else:
        p = h[i][0]
        k = 0
        h[i].append(str(p).zfill(6) + str(k + 1).zfill(6))
        break
h = sorted(h,key=lambda h:h[2])
# print(h)
for i in range(M):
    print(h[i][3])

### FIXED CODE ###

N,M = map(int,input().split())
h = [list(map(int, input().split()))for i in range(M)]
for i in range(M):
    h[i].append(i)
h = sorted(h,key=lambda h:(h[0],h[1]))
k = 0
p = h[0][0]
for i in range(M):
    if h[i][0] == p:
        h[i].append(str(p).zfill(6)+str(k+1).zfill(6))
        k+=1
    else:
        p = h[i][0]
        k = 0
        h[i].append(str(p).zfill(6) + str(k + 1).zfill(6))
        k += 1
# print(h)
h = sorted(h,key=lambda h:h[2])
# print(h)
for i in range(M):
    print(h[i][3])
a,b,c=list(input().split())
u=[[a],[b],[c]]
print(a(0)+b(0)+c(0))

### FIXED CODE ###

a,b,c=map(str,input().split())
print(a[0]+b[0]+c[0])
n = int(input())
p = list(map(int, input().split()))

cnt = 0
for i in range(n):
    if p[i] == i + 1:
        if p[i - 1] == i + 1:
            p[i], p[i - 1] = p[i - 1], p[i]
        else:
            p[i], p[i + 1] = p[i + 1], p[i]
        cnt += 1

print(cnt)

### FIXED CODE ###

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

cnt = 0
for i in range(n):
    if p[i] == i + 1:
        if i == 0:
            p[i], p[i + 1] = p[i + 1], p[i]
        elif i == n-1:
            p[i], p[i - 1] = p[i - 1], p[i]
        else:
            if p[i - 1] == i + 1:
                p[i], p[i - 1] = p[i - 1], p[i]
            else:
                p[i], p[i + 1] = p[i + 1], p[i]
        cnt += 1

print(cnt)
from functools import lru_cache
N, M = map(int, input().split())

mod = 10**9+7

a = [1] * (N+1)
for _ in range(M):
    a[int(input())] = 0

@lru_cache()
def f(x):
    v = 0
    if x<0:
        return 0
    if x == 0:
        return 1
    if a[x-1]:
        v += f(x-1)
    if a[x-2]:
        v += f(x-2)
    v %= mod
    return v

print(f(N))

### FIXED CODE ###

from functools import lru_cache
import sys
sys.setrecursionlimit(1000000)

N, M = map(int, input().split())
mod = 10**9+7

a = [1] * (N+1)
for _ in range(M):
    a[int(input())] = 0

@lru_cache()
def f(x):
    v = 0
    if x<0:
        return 0
    if x == 0:
        return 1
    if a[x-1]:
        v += f(x-1)
    if a[x-2]:
        v += f(x-2)
    v %= mod
    return v

print(f(N))
def get_path(start, goal, pred):
    return get_path_row(start, goal, pred[start])


def get_path_row(start, goal, pred_row):
    path = []
    i = goal
    while i != start and i >= 0:
        path.append(i)
        i = pred_row[i]
    if i < 0:
        return []
    path.append(i)
    return path[::-1]


def main():
    from scipy.sparse.csgraph import bellman_ford
    from scipy.sparse import csr_matrix
    from scipy.sparse.csgraph._shortest_path import NegativeCycleError
    import sys
    input = sys.stdin.buffer.readline
    N, M, P = (int(i) for i in input().split())
    g = [[10**6]*N for _ in range(N)]
    ban_v = set()
    for i in range(M):
        a, b, c = (int(i) for i in input().split())
        c -= P
        if a == b:
            ban_v.add(a-1)
        else:
            g[a-1][b-1] = -c

    csr = csr_matrix(g)
    ans = -1
    try:
        dist, p = bellman_ford(csr, return_predecessors=True)
        path = get_path(0, N-1, p)
        if any(v in ban_v for v in path):
            ans = -1
        else:
            ans = max(0, int(dist[0][N-1]*-1))
    except NegativeCycleError:
        ans = -1
    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    from itertools import product
    import sys
    input = sys.stdin.buffer.readline
    N, M, P = (int(i) for i in input().split())
    adj_list = [[] for _ in range(N)]
    radj_list = [[] for _ in range(N)]
    ok = [False]*N
    edge = []
    for i in range(M):
        a, b, c = (int(i) for i in input().split())
        c -= P
        adj_list[a-1].append(b-1)
        radj_list[b-1].append(a-1)
        edge.append((a-1, b-1, -c))

    def dfs(G, v):
        seen = [False]*N
        todo = [v]
        seen[v] = True
        while todo:
            u = todo.pop()
            for next_v in G[u]:
                if seen[next_v]:
                    continue
                seen[next_v] = True
                todo.append(next_v)
        return seen

    i = 0
    for s, rs in zip(dfs(adj_list, 0), dfs(radj_list, N-1)):
        ok[i] = s and rs
        i += 1

    # Bellman_ford
    d = [10**12]*N
    d[0] = 0
    update = True
    step = 0
    while update:
        update = False
        for a, b, c in edge:
            if not(ok[a]) or not(ok[b]):
                continue
            newD = d[a] + c
            if newD < d[b]:
                update = True
                d[b] = newD
        step += 1
        if step > N:
            return print(-1)
    print(max(0, d[N-1]*-1))


if __name__ == '__main__':
    main()