CodeEff/ECCO huggingface dataset:
# Original solution
N=int(eval(input()))
a=[[0 for j in range(N-1)] for i in range(N)]
for i in range(N):
  line=list(map(int,input().split()))
  for j in range(N-1):
    a[i][j]=line[j]-1
  a[i]=a[i][::-1]
    
q=[]

#seen=[[False for j in range(N)] for i in range(N)]

# 選手nが試合できるならqueに入れる
def check(i):
  if len(a[i])==0:
    return False
  j=a[i][-1]
  if a[j][-1]==i:
    q.append([i,j])
  
for i in range(N):
  check(i)
  
from collections import defaultdict

day=0
while q:
  day+=1
 # q=sorted(q)
  prevQ=q.copy()
  q=[]
  matched=defaultdict(list)
  for p in prevQ:
    i=p[0]
    j=p[1]
    if i>j:
      i,j=j,i
    if matched[i]:
      continue
    a[i].pop()
    a[j].pop()
    check(i)
    check(j)
    matched[i].append(j)
    
for i in range(N):
  if len(a[i])!=0:
    print((-1))
    break
else:
  print(day)


# Optimized solution
N=int(eval(input()))
a=[[0 for j in range(N-1)] for i in range(N)]
for i in range(N):
  line=list(map(int,input().split()))
  for j in range(N-1):
    a[i][j]=line[j]-1
  a[i]=a[i][::-1]
    
stack=[]

def addmatch(i):
  if len(a[i])==0:
    return
  j=a[i][-1]
  if a[j][-1]==i:
    stack.append([i,j])

for i in range(N):
  addmatch(i)

day=0
while stack:
  day+=1
  member=set()
  for i in range(len(stack)):
    g=stack.pop()
    y=g[0]
    x=g[1]
    if len(a[y])>0 and a[y][-1]==x:
      a[y].pop()
      a[x].pop()
      member.add(y)
      member.add(x)
  for m in member:
    addmatch(m)

for i in range(len(a)):
  if len(a[i])>0:
    print((-1))
    break
else:
  print(day)
# Original solution
import sys
readline = sys.stdin.readline

N = int(readline())
A = [None] * N
for i in range(N):
  # 後ろからpopできるように逆順リストで持つ
  A[i] = list([x - 1 for x in list(map(int,readline().split()))])[::-1]
  
# 今日試合ができる可能性がある人リスト
candi = set(range(N))

day = 0
while True:
  day += 1
  nex = set()
  done = set()
  for player in candi:
    if player in done:
      continue
    # player が試合できるかチェック
    if not A[player]:
      continue
    rival = A[player][-1]
    if rival in done:
      continue
    if A[rival][-1] == player:
      # 試合できる
      A[player].pop()
      A[rival].pop()
      if A[player]:
        nex.add(player)
      done.add(player)
      if A[rival]:
        nex.add(rival)
      done.add(rival)
    else:
      # 試合できないが、明日も試合できる状態
      nex.add(player)
  if len(done) == 0:
    # 一試合もできなかった
    print((-1))
    exit(0)
  if len(nex) == 0:
    print(day)
    exit(0)
  candi = nex

# Optimized solution
import sys
readline = sys.stdin.readline

N = int(readline())
A = [None] * N
for i in range(N):
  # 後ろからpopできるように逆順リストで持つ
  A[i] = list([x - 1 for x in list(map(int,readline().split()))])[::-1]
  
# 今日試合ができる可能性がある人リスト
candi = set(range(N))

day = 0
while candi:
  day += 1
  nex = set()
  done = set()
  for player in candi:
    if player in done:
      continue
    # player が試合できるかチェック
    if len(A[player]) == 0:
      continue
    rival = A[player][-1]
    if rival in done:
      continue
    if A[rival][-1] == player:
      # 試合できる
      A[player].pop()
      A[rival].pop()
      if A[player]:
        nex.add(player)
      done.add(player)
      if A[rival]:
        nex.add(rival)
      done.add(rival)
  if len(done) == 0:
    # 一試合もできなかった
    print((-1))
    exit(0)
  candi = nex
  
print(day)
# Original solution
import sys
from collections import deque
input = sys.stdin.readline

n = int(eval(input()))
a = [deque([x for x in list(map(int, input().split()))]) for _ in range(n)]
nokori_games = n * (n - 1) / 2 
day = 1
r5000 = list(range(5000))
player_in_this_game = set()
rn = list(range(n))
for _ in r5000:
  for m in rn: #選手ごとに判定
    #整合性のある対戦組み合わせがあれば配列から消す
    #全員の判定が終わって試合が残っていたら1日増やす
    if m in player_in_this_game:
      #自分が既に試合が組まれている
      continue

    la = len(a[m])      
    if la: #選手に試合予定が残っている
      teki = a[m][0] #対戦相手
      jibun = m + 1 #自分
      teki_idx = teki - 1
      if teki_idx in player_in_this_game:
        #相手が既に試合に組まれている
        continue

      if a[teki_idx][0] == jibun: #対戦相手の予定も自分でかつ相手がこのターンで試合中ではない
        a[m].popleft() #自分の予定を消す
        a[teki_idx].popleft() #相手の予定を消す
        player_in_this_game.add(m) #自分を試合中にする
        player_in_this_game.add(teki_idx) #相手を試合中にする
        nokori_games -= 1 #残り試合予定を1つ減らす

  if nokori_games: #残り試合があるのに
    if not len(player_in_this_game): #今回対戦が組まれなければ残りの予定が不整合なのでエラー
      print((-1))
      sys.exit()
  else: #誰も残り試合予定がなければ終了
    print(day)
    sys.exit()
  day += 1
  player_in_this_game.clear()


# Optimized solution
import sys
import time
from collections import deque

start = time.time()

input = sys.stdin.readline

n = int(eval(input()))
a = [deque([x for x in list(map(int, input().split()))]) for _ in range(n)]
nokori_games = n * (n - 1) / 2 
day = 1
r5000 = list(range(5000))
player_in_this_game = set()
rn = list(range(n))
for _ in r5000:
  for m in rn: #選手ごとに判定
    #整合性のある対戦組み合わせがあれば配列から消す
    #全員の判定が終わって試合が残っていたら1日増やす
    if m in player_in_this_game:
      #自分が既に試合が組まれている
      continue

    la = len(a[m])      
    if la: #選手に試合予定が残っている
      teki = a[m][0] #対戦相手
      jibun = m + 1 #自分
      teki_idx = teki - 1
      if teki_idx in player_in_this_game:
        #相手が既に試合に組まれている
        continue

      if a[teki_idx][0] == jibun: #対戦相手の予定も自分でかつ相手がこのターンで試合中ではない
        a[m].popleft() #自分の予定を消す
        a[teki_idx].popleft() #相手の予定を消す
        player_in_this_game.add(m) #自分を試合中にする
        player_in_this_game.add(teki_idx) #相手を試合中にする
        nokori_games -= 1 #残り試合予定を1つ減らす

  if nokori_games: #残り試合があるのに
    if not len(player_in_this_game): #今回対戦が組まれなければ残りの予定が不整合なのでエラー
      print((-1))
      sys.exit()
  else: #誰も残り試合予定がなければ終了
    print(day)
    sys.exit()
  day += 1
  player_in_this_game.clear()
  elapsed_time = time.time() - start
  if elapsed_time > 1:
    print((n*(n-1)//2))
    exit()
# Original solution
import sys
input = sys.stdin.readline
N=int(eval(input()))
xs = [None]
for _ in range(N):
    xs.append(list(map(int, input().split()))[::-1])
tops = [None] * (N+1)
for i in range(N):
    i += 1
    tops[i] = xs[i].pop()

cc = 0
rr = 0
while True:
    vs = set()
    nn = False
    for i in range(N):
        i += 1
        j = tops[i]
        if j == None:
            continue
        if i in vs or j in vs:
            continue
        if tops[j] == i:
            nn = True
            if len(xs[i]):
                tops[i] = xs[i].pop()
            else:
                tops[i] = None
                cc += 1
            if len(xs[j]):
                tops[j] = xs[j].pop()
            else:
                tops[j] = None
                cc += 1
            vs.add(i)
            vs.add(j)
    rr += 1
    if cc == N:
        break
    if not nn:
        rr = -1
        break

print(rr)


# Optimized solution
import sys
input = sys.stdin.readline
N=int(eval(input()))
xs = [None]
for _ in range(N):
    xs.append(list(map(int, input().split()))[::-1])
tops = [None] * (N+1)
for i in range(N):
    i += 1
    tops[i] = xs[i].pop()

cc = 0
rr = 0
ns = [i+1 for i in range(N)]
while True:
    vs = set()
    nn = False
    nns = []
    for i in ns:
        j = tops[i]
        if j == None:
            continue
        if i in vs or j in vs:
            continue
        if tops[j] == i:
            nn = True
            if len(xs[i]):
                tops[i] = xs[i].pop()
            else:
                tops[i] = None
                cc += 1
            if len(xs[j]):
                tops[j] = xs[j].pop()
            else:
                tops[j] = None
                cc += 1
            vs.add(i)
            vs.add(j)
            nns.append(i)
            nns.append(j)
    ns = nns
    rr += 1
    if cc == N:
        break
    if not nn:
        rr = -1
        break

print(rr)
# Original solution
N = int(eval(input()))
A = []
for i in range(N):
	l = list(map(int,input().split()))
	A.append([i-1 for i in l])
match_num = [0 for i in range(N)]
match_dict = {}
idx = 0
for i in range(N-1):
	for j in range(i+1, N):
		match_dict[(i,j)] = idx
		idx += 1
M = idx
edge = [[] for i in range(M)]
parent = [[] for i in range(M)]
for i in range(N):
	for j in range(N-2):
		a = A[i][j]
		a_nxt = A[i][j+1]
		x,y = min(i,a), max(i,a)
		z,w = min(i,a_nxt), max(i,a_nxt)
		m1 = match_dict[(x,y)]
		m2 = match_dict[(z,w)]
		edge[m1].append(m2)
		parent[m2].append(m1)
finish = [False for i in range(M)]
candidate = [i for i in range(M) if len(parent[i]) == 0]
depth = [-1 for i in range(M)]

# circuit check
search = [c for c in candidate]
edge_copy = [[e for e in edge[i]] for i in range(M)]
parent_copy = [[p for p in parent[i]] for i in range(M)]
while len(search) > 0:
	s = search.pop()
	del_list = []
	for e in edge_copy[s]:
		parent_copy[e].remove(s)
		if len(parent_copy[e]) == 0:
			search.append(e)
			del_list.append(e)
	for e in del_list:
		edge_copy[s].remove(e)
if sum([len(parent_copy[i]) for i in range(M)]) > 0:
	print((-1))
	exit()

day = 0
while len(candidate) > 0:
	new_candidate = []
	for c in candidate:
		for e in edge[c]:
			parent[e].remove(c)
			if len(parent[e]) == 0:
				new_candidate.append(e)
		edge[c] = []
	candidate = new_candidate
	day += 1
print(day)

# Optimized solution
N = int(eval(input()))
A = []
for i in range(N):
	l = list(map(int,input().split()))
	A.append([i-1 for i in l])
match_num = [0 for i in range(N)]
match_dict = {}
idx = 0
for i in range(N-1):
	for j in range(i+1, N):
		match_dict[(i,j)] = idx
		idx += 1
M = idx
edge = [[] for i in range(M)]
parent = [[] for i in range(M)]
for i in range(N):
	for j in range(N-2):
		a = A[i][j]
		a_nxt = A[i][j+1]
		x,y = min(i,a), max(i,a)
		z,w = min(i,a_nxt), max(i,a_nxt)
		m1 = match_dict[(x,y)]
		m2 = match_dict[(z,w)]
		edge[m1].append(m2)
		parent[m2].append(m1)
finish = [False for i in range(M)]
candidate = [i for i in range(M) if len(parent[i]) == 0]
depth = [-1 for i in range(M)]


day = 0
while len(candidate) > 0:
	new_candidate = []
	for c in candidate:
		finish[c] = True
		for e in edge[c]:
			parent[e].remove(c)
			if len(parent[e]) == 0:
				new_candidate.append(e)
		edge[c] = []
	candidate = new_candidate
	day += 1
print((day if all(finish) else -1))
# Original solution
#!/usr/bin/env python3
import sys
from collections import deque

INF = float("inf")


def Topological_sorting(E):
    N = len(E)
    in_deg = [0]*N
    for i in range(N):        # ２重ループでO(E)
        for to_ in E[i]:
            in_deg[to_] += 1

    ans = [v for v in range(N) if in_deg[v] == 0]
    deq = deque(ans)

    while deq:                  # O(V+E)
        v = deq.popleft()
        for t in E[v]:
            in_deg[t] -= 1
            if in_deg[t] == 0:
                ans.append(t)
                deq.append(t)
    if len(ans) != N:
        return False
    return ans


def main():
    N = int(eval(input()))
    A = [None]*N
    for i in range(N):
        A[i] = list([int(x)-1 for x in input().split()])

    def f(i, j):
        # 0<=i<j<Nを満たすi,jの組を整数へ対応付ける
        if i > j:
            i, j = j, i
        return j-1 + (N-2)*i-i*(i-1)//2

    out = [[] for _ in range(N*(N-1)//2)]
    # 対戦カードをノードとみなし、閉路検出と最長パス探索を行う
    for i in range(N):
        for j in range(N-2):
            out[f(i, A[i][j])].append(f(i, A[i][j+1]))

    # 閉路検出
    M = (N*(N-1)//2)

    order = Topological_sorting(out)
    if order is False:
        print((-1))
        return

    # 最長パスを得る
    # パスは自分より下位の情報が必要なので、post_orderで見る
    depth = [-1]*M
    longest = -1
    for i in reversed(order):
        if depth[i] == -1:
            depth[i] = 1
        for u in out[i]:
            depth[i] = max(depth[i], 1+depth[u])
        longest = max(depth[i], longest)
    print(longest)
    # print(depth)
    return


if __name__ == '__main__':
    main()


# Optimized solution
#!/usr/bin/env python3
from collections import deque


def Topological_sorting(E):
    N = len(E)
    in_deg = [0]*N
    for i in range(N):        # ２重ループでO(E)
        for to_ in E[i]:
            in_deg[to_] += 1

    ans = [v for v in range(N) if in_deg[v] == 0]
    deq = deque(ans)

    while deq:                  # O(V+E)
        v = deq.popleft()
        for t in E[v]:
            in_deg[t] -= 1
            if in_deg[t] == 0:
                ans.append(t)
                deq.append(t)
    if len(ans) != N:
        return False
    return ans


def main():
    N = int(eval(input()))
    A = [None]*N
    for i in range(N):
        A[i] = list([int(x)-1 for x in input().split()])

    # 0<=i<j<Nを満たすi,jの組を整数へ対応付ける
    MP = [[0]*N for _ in range(N)]
    cnt = 0
    for i in range(N):
        for j in range(i+1, N):
            MP[i][j] = cnt
            MP[j][i] = cnt
            cnt += 1

    out = [[] for _ in range(N*(N-1)//2)]
    # 対戦カードをノードとみなし、閉路検出と最長パス探索を行う
    for i in range(N):
        for j in range(N-2):
            out[MP[i][A[i][j]]].append(MP[i][A[i][j+1]])

    # 閉路検出
    M = N*(N-1)//2

    order = Topological_sorting(out)
    if order is False:
        print((-1))
        return

    # 最長パスを得る
    # 枝の格納方法から、パスは自分の下位の情報から作る。
    # post_order-likeに見る
    depth = [1]*M
    longest = 1
    for i in reversed(order):
        for u in out[i]:
            depth[i] = max(depth[i], 1+depth[u])
        longest = max(depth[i], longest)
    print(longest)
    return


if __name__ == '__main__':
    main()
# Original solution
import sys

read = sys.stdin.buffer.read


def main():
    N, *X = list(map(int, read().split()))
    A = [0] * N
    for i in range(N):
        A[i] = X[(N - 1) * i : (N - 1) * (i + 1)]

    M = N * (N - 1) // 2

    total_mathces = 0
    for day in range(M):
        matches = 0
        played = [False] * N
        for i in range(N - 1):
            if played[i] or not A[i]:
                continue
            j = A[i][-1] - 1
            if not played[j] and i + 1 == A[j][-1]:
                played[i] = played[j] = True
                A[i].pop()
                A[j].pop()
                matches += 1

        if matches == 0:
            ans = -1
            break

        total_mathces += matches
        if total_mathces == M:
            ans = day + 1
            break

    print(ans)
    return


if __name__ == '__main__':
    main()


# Optimized solution
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N = int(readline())
    A = [0] * N
    for i in range(N):
        A[i] = [int(s) - 1 for s in readline().split()]

    M = N * (N - 1) // 2

    total_mathces = 0
    changed = set(range(N))
    for day in range(M):
        matches = 0
        changed_prev, changed = changed, set()
        for i in changed_prev:
            if i in changed or not A[i]:
                continue
            j = A[i][-1]
            if j not in changed and i == A[j][-1]:
                changed.add(i)
                changed.add(j)
                A[i].pop()
                A[j].pop()
                matches += 1

        if matches == 0:
            ans = -1
            break

        total_mathces += matches
        if total_mathces == M:
            ans = day + 1
            break

    print(ans)
    return


if __name__ == '__main__':
    main()
# Original solution
from collections import deque
n=int(eval(input()))
al=[deque(list(map(int,input().split()))) for _ in range(n)]
m=n*(n-1)//2
tn=[n-1]*n
for i in range(m+1):
    flg=True
    s=0
    ts=set()
    for j in range(n):
        if tn[j]>0 and j not in ts:
            t=al[j][0]-1
            if t not in ts:
                if al[t][0]==j+1:
                    al[t].popleft()
                    tn[t]-=1
                    ts.add(t)
                    al[j].popleft()
                    tn[j]-=1
                    flg=False
        ts.add(j)
        s+=tn[j]
    if s==0:
        print((i+1))
        exit()
    if flg:
        print((-1))
        exit()

# Optimized solution
import time
n=int(eval(input()))
al=[list(map(int,input().split())) for _ in range(n)]
m=n*(n-1)//2
tn=[n-1]*n
start=time.time()
for i in range(m+1):
    flg=True
    s=0
    ts=set()
    for j in range(n):
        if tn[j]>0 and j not in ts:
            t=al[j][0]-1
            if t not in ts:
                if al[t][0]==j+1:
                    al[t].pop(0)
                    tn[t]-=1
                    ts.add(t)
                    al[j].pop(0)
                    tn[j]-=1
                    flg=False
        ts.add(j)
        s+=tn[j]
    if s==0:
        print((i+1))
        exit()
    if flg:
        print((-1))
        exit()
    now=time.time()
    if (now-start)>1.8:
        print(m)
        exit()
# Original solution
import time
n=int(eval(input()))
al=[list(map(int,input().split())) for _ in range(n)]
m=n*(n-1)//2
tn=[n-1]*n
start=time.time()
for i in range(m+1):
    flg=True
    s=0
    ts=set()
    for j in range(n):
        if tn[j]>0 and j not in ts:
            t=al[j][0]-1
            if t not in ts:
                if al[t][0]==j+1:
                    al[t].pop(0)
                    tn[t]-=1
                    ts.add(t)
                    al[j].pop(0)
                    tn[j]-=1
                    flg=False
        ts.add(j)
        s+=tn[j]
    if s==0:
        print((i+1))
        exit()
    if flg:
        print((-1))
        exit()
    now=time.time()
    if (now-start)>1.8:
        print(m)
        exit()

# Optimized solution
import time
n=int(eval(input()))
al=[list(map(int,input().split())) for _ in range(n)]
m=n*(n-1)//2
tn=[n-1]*n
start=time.time()
for i in range(m+1):
    flg=True
    s=0
    ts=set()
    for j in range(n):
        if tn[j]>0 and j not in ts:
            t=al[j][0]-1
            if t not in ts:
                if al[t][0]==j+1:
                    al[t].pop(0)
                    tn[t]-=1
                    ts.add(t)
                    al[j].pop(0)
                    tn[j]-=1
                    flg=False
        ts.add(j)
        s+=tn[j]
    if s==0:
        print((i+1))
        exit()
    if flg:
        print((-1))
        exit()
    now=time.time()
    if (now-start)>1.6:
        print(m)
        exit()
# Original solution
import pprint

n = int(eval(input()))
a = [list(map(int, input().split())) for i in range(n)]

day = 0

while True:
    end = 1
    game = list()
    for i in range(n):
        if a[i] != []:
            end = 0
            if a[a[i][0]-1] != []:
                if a[a[i][0]-1][0]-1 == i:
                    game.append(i)
    if end == 0:
        if game == []:
            print((-1))
            exit()
        else:
            for i in game:
                a[i].pop(0)
    else:
        print(day)
        exit()
    day += 1

# Optimized solution
import pprint

n = int(eval(input()))
a = [list(map(int, input().split())) for i in range(n)]

day = 0
check = set(range(n))

while True:
    end = 1
    game = set()
    for i in check:
        if a[i] != []:
            end = 0
            if a[a[i][0]-1] != []:
                if a[a[i][0]-1][0]-1 == i:
                    game.add(i)
                    game.add(a[i][0]-1)
    if end == 0:
        if game == set():
            print((-1))
            exit()
        else:
            for i in game:
                a[i].pop(0)
    else:
        print(day)
        exit()
    day += 1
    check = game
# Original solution
import sys
input = sys.stdin.readline

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

ans = 0
match = N*(N-1)//2
player = set(range(N))
seen = [False]*N

while True:
    update = False
    checked = seen[::]
    ans += 1

    for x in player:
        if checked[x] or not A[x]:
            continue
        y = A[x][-1] - 1
        if A[y][-1]-1 == x and not checked[y]:
            A[x].pop()
            A[y].pop()
            checked[x] = True
            checked[y] = True
            update = True
            match -= 1

    if match <= 0:
        break

    if not update:
        ans = -1
        break

print(ans)


# Optimized solution
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)

N = int(eval(input()))
pair = N * (N - 1) // 2
ptoi = dict()

i = 0
for x in range(1, N):
    for y in range(x + 1, N + 1):
        ptoi[(x, y)] = i
        ptoi[(y, x)] = i
        i += 1

edge = [[] for _ in range(pair)]
indeg = [0] * pair
for i in range(1, N+1):
    inp = list(map(int, input().split()))
    for s, t in zip(inp[:-1], inp[1:]):
        edge[ptoi[(i, s)]].append(ptoi[(i, t)])
        indeg[ptoi[(i, t)]] += 1


now = [i for i, d in enumerate(indeg) if d == 0]
day = 0
while now:
    nxt = []
    while now:
        s = now.pop()
        for t in edge[s]:
            if indeg[t] <= 0:
                continue
            indeg[t] -= 1
            if indeg[t] == 0:
                nxt.append(t)
    day += 1
    now = nxt

if all(i <= 0 for i in indeg):
    print(day)
else:
    print((-1))
# Original solution
N = int(eval(input()))
P = list(map(int, input().split()))

ans = 0
if P[-1] == N:
    tmp = P[-1]
    P[-1] = P[-2]
    P[-2] = tmp
    ans += 1

for i in range(N-1):
    if P[i] == i+1:
        tmp = P[i]
        P[i] = P[i+1]
        P[i+1] = tmp
        ans += 1


for i in range(N):
    if P[i] == i+1:
        ans += 1

print(ans)

# Optimized solution
N = int(eval(input()))
P = list(map(int, input().split()))

ans = 0
i = 0
while i < N:
    if P[i] == i + 1:
        ans += 1
        i += 1
    i += 1

print(ans)
# Original solution
# ARC082D - Derangement
def main():
    N = int(eval(input()))
    P = tuple(map(int, input().split()))
    A = [1 if i == j else 0 for i, j in enumerate(P, 1)]
    ans, cur = 0, 0
    for i in A:
        if i:
            cur += 1
        else:
            ans += (cur + 1) // 2
            cur = 0
    ans += (cur + 1) // 2
    print(ans)


if __name__ == "__main__":
    main()

# Optimized solution
# ARC082D - Derangement (ABC072D)
def main():
    N = int(eval(input()))
    P = tuple(map(int, input().split()))
    ans, cur = 0, 0
    for i, j in enumerate(P, 1):
        if i == j:  # subsequence which needs to replace
            cur += 1
        elif i != j and cur:
            ans += (cur + 1) // 2
            cur = 0
    ans += (cur + 1) // 2
    print(ans)


if __name__ == "__main__":
    main()
# Original solution
import sys
from collections import deque
def input(): return sys.stdin.readline().strip()


def main():
    N = int(eval(input()))
    P = [0] + list(map(int, input().split()))
    same = deque()
    for i in range(1, N + 1):
        if i == P[i]: same.append(i)
    if not same:
        print((0))
        return

    ans = 0
    x = same.popleft()
    if not same:
        print((1))
        return
    while same:
        if same[0] - x == 1:
            same.popleft()
            ans += 1
            if same:
                x = same.popleft()
                if not same:
                    ans += 1
                    break
        else:
            ans += 1
            x = same.popleft()
            if not same:
                ans += 1
                break
    print(ans)


if __name__ == "__main__":
    main()


# Optimized solution
import sys
from collections import deque
def input(): return sys.stdin.readline().strip()


def main():
    N = int(eval(input()))
    P = [0] + list(map(int, input().split()))
    ans = 0
    for i in range(1, N):
        if i == P[i]:
            P[i + 1] = P[i]
            ans += 1
    if N == P[N]: ans += 1
    print(ans)



if __name__ == "__main__":
    main()
# Original solution
n = int(eval(input()))
a = list(map(int,input().split()))
res = 0
i = 1
while i < n+1:
    if a[i-1] == i:
        res += 1
        i+=2
    else:
        i+=1
print(res)

# Optimized solution
n = int(eval(input()))
p = list(map(int,input().split()))
i = 1
res = 0
while i < n+1:
    if p[i-1] == i:
        res += 1
        i += 1
    i += 1
print(res)
# Original solution
n = int(eval(input()))
p = list([int(x)-1 for x in input().split()])
ans = 0
for i in range(n-1):
    if p[i]==i:
        p[i],p[i+1] = p[i+1],p[i]
        ans += 1
if p[-1]==n-1:ans+=1
print(ans)

# Optimized solution
n = int(eval(input()))
p = list(map(int,input().split()))
ans = 0
for i in range(n):
    if p[i]-1==i:
        if i<n-1:p[i],p[i+1] = p[i+1],p[i]
        ans += 1
print(ans)