시공간 스고로쿠 로드
시간 제한8초메모리 제한512 MB
각 칸 i에는 pi만큼 강제로 이동시키는 효과가 있고, 효과가 연쇄적으로 이어지다 효과가 없는 칸에서 멈춘다. 1번 칸에서 N번 칸 또는 그 너머에 도달하는 최소 주사위 굴림 횟수를 구하되, 무한 루프에 빠지는 칸은 피해야 한다. 주사위 눈은 1부터 6까지이며 1번과 N번 칸의 효과는 항상 0이다. 주어진 판은 반드시 끝낼 수 있다. 효과 이동의 종착점을 미리 계산하면 그래프 최단 경로 문제가 된다. N은 최대 100,000이고 pi의 절댓값은 100,000 이하이다. 무한 루프는 사이클로 검출하며, 사이클에 속한 칸에 도착하면 실패로 본다. 정답은 필요한 최소 굴림 횟수를 출력한다. 방문 처리는 칸 단위로 하며, 각 칸에서 6번의 전이를 확인하면 선형 시간에 해결된다. 주사위 결과를 원하는 대로 정할 수 있으므로 매 굴림에서 1부터 6까지 모두 시도할 수 있다. 효과 연쇄는 반복문 대신 경로 압축으로 한 번에 계산해도 되고, 시뮬레이션으로 따라가도 전체 시간이 충분하다. 사이클이 없는 칸만 그래프의 정점으로 두고, 도달 가능한 칸에 대해 BFS를 수행한다. 목표에 도달하거나 목표를 넘어서면 즉시 종료한다.
문제
전 시공간 통일 차원 스고로쿠 토너먼트. 500조 명이 넘는 참가자 중에서 단 한 명의 스고로쿠 절대王者를 가리는 그 대회에, 당신은 21세기 지구 대표로 참가하고 있다.
지금 당신이 도전하고 있는 과제는 자기 자신을 말로 삼은 1차원 스고로쿠다. 끝의 시작 칸에서 출발해서, 1부터 6까지의 눈이 하나씩 적힌 거대한 6면 주사위를 굴려 나온 눈의 수만큼 전진하기를 반복하는, 당신도 잘 아는 형식의 스고로쿠다. 시작 칸과 반대쪽 끝에 있는 도착 칸에 멈추면 골인이다. 물론 골인할 때까지 주사위를 굴린 횟수가 적을수록 좋은 성적을 얻는다.
칸 중에는 특수한 효과를 가진 칸 "○칸 전진"과 "○칸 후퇴"가 있어서, 거기에 멈추고 말면 지정된 칸 수만큼 전진하거나 후퇴해야 한다. 칸의 효과로 이동한 결과 다시 효과가 있는 칸에 멈춘 경우에는 이어서 지시대로 이동한다.
하지만 이것은 한 번에 공략할 수 없는 시공간 스고로쿠다. 두려운 점은, 예를 들어 "3칸 전진"의 3칸 앞에 "3칸 후퇴"가 놓여 있을 수도 있다는 것이다. 이런 칸에 멈춰서 칸의 효과로 무한 루프에 빠져 버린 경우에는 영원히 칸을 왕복해야 한다.
다행히도 당신의 몸에는, 원하는 사건을 전사건으로 바꿀 수 있는 이능 '확률 왜곡'이 깃들어 있다. 이 능력을 쓰면 주사위의 눈을 자유로이 조종하는 것도 가능하다. 이 이점을 살려서 무한 루프에 빠지지 않도록 하면서 나아갈 때, 골인할 때까지 주사위를 굴리는 횟수의 최솟값은 얼마가 될까.
입력
N
p1
p2
.
.
.
pN
입력의 첫째 줄에는 정수 N (3 ≤ N ≤ 100,000)이 적혀 있다. 이것은 스고로쿠의 칸 수를 나타낸다. 칸에는 1번부터 N번까지 번호가 붙어 있다. 시작 칸이 1번이고, 그다음부터 시작에 가까운 순서로 2번, 3번, ..., N - 1번이 이어지며, 도착 칸이 N번이다. i번 칸에서 주사위를 굴려 j의 눈이 나오면 i + j번 칸으로 이동한다. 다만 i + j가 N을 넘으면 남은 수만큼 되돌아가지 않고 골인한 것으로 본다.
이어지는 N줄에는 정수 pi (-100,000 ≤ pi ≤ 100,000)가 적혀 있다. 1 + i번째 줄에 적힌 정수 pi는 i번 칸에 적힌 지시를 나타낸다. pi > 0이면 "pi칸 전진", pi < 0이면 "-pi칸 후퇴"이고, pi = 0이면 그 칸에는 아무 효과도 없다. p1과 pN은 항상 0이다. 칸의 효과로 시작보다 앞이나 도착보다 뒤로 이동하라고 지시되는 일은 없다.
주어진 스고로쿠는 골인할 수 있다고 가정해도 좋다.
출력
골인할 때까지 주사위를 굴리는 횟수의 최솟값을 출력하라.