만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

점프 점프

면접 대비

시간 제한2초메모리 제한512 MB

요약
돌 n개에 적힌 점프 거리가 주어질 때, 시작 돌에서 왼쪽이나 오른쪽으로 뛰어 다리 안에 머무르며 도달할 수 있는 돌의 개수를 센다.
난이도

보통10점 중 4점

유형
그래프, BFS, 배열, 큐
정답자
아직 제출이 없습니다

문제

영우는 개구리다. 개굴개굴개굴.

영우는 돌 nn개가 일렬로 놓인 돌다리 위에 있다. 돌에는 왼쪽부터 1번, 2번, 차례로 nn번까지 번호가 붙어 있고, 각 돌에는 숫자가 하나씩 적혀 있다. ii번 돌에 적힌 수가 AiA_i일 때, 영우는 ii번 돌에서 왼쪽으로 AiA_i칸 떨어진 i−Aii - A_i번 돌이나 오른쪽으로 AiA_i칸 떨어진 i+Aii + A_i번 돌로 점프할 수 있다. 돌다리 밖으로는 나갈 수 없으므로 도착 번호가 1보다 작거나 nn보다 큰 점프는 하지 못한다.

어떤 돌을 방문 가능하다는 것은 출발한 돌에서 점프를 몇 번 해서 그 돌에 닿을 수 있다는 뜻이다. 출발한 돌도 방문 가능한 돌로 센다.

출발점이 주어지면 영우가 방문 가능한 돌의 개수를 구하라.

입력

첫째 줄에 돌다리의 돌 개수 nn이 주어진다. (1≤n≤1000001 \le n \le 100000)

둘째 줄에 각 돌에서 점프할 수 있는 거리 A1,A2,…,AnA_1, A_2, \dots, A_n이 공백으로 구분되어 주어진다. (1≤Ai≤1000001 \le A_i \le 100000)

셋째 줄에 출발점 ss가 주어진다. (1≤s≤n1 \le s \le n)

출력

첫째 줄에 영우가 방문 가능한 돌의 개수를 출력한다.

예제1

  1. 예제 1

    입력
    5
    1 4 2 2 1
    3
    
    예상 출력
    5