점프 점프 2

면접 대비

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

요약

각 돌에서 A_i만큼 좌우로 점프할 수 있을 때 시작점 s에서 도달 가능한 돌의 수를 세되, 한 번 이상 점프해 s로 돌아올 수 있을 때만 s를 포함한다.

난이도: 보통10점 중 5점
유형: 그래프, BFS, 구현, 수학
정답자: 아직 제출이 없습니다

문제

개구리 영우가 돌 $n$ 개가 일렬로 놓인 돌다리 위에 있다. 돌에는 왼쪽부터 $1$ 번에서 $n$ 번까지 번호가 붙어 있고, $i$ 번 돌에는 숫자 $A_i$ 가 하나 적혀 있다. 영우는 $i$ 번 돌에서 왼쪽이나 오른쪽으로 정확히 $A_i$ 칸 떨어진 돌, 즉 $i - A_i$ 번 돌이나 $i + A_i$ 번 돌로 점프할 수 있다. 번호가 $1$ 보다 작거나 $n$ 보다 큰 자리로는 점프할 수 없다.

영우는 $s$ 번 돌에서 출발한다. 점프 횟수에는 제한이 없고, 같은 돌을 여러 번 밟아도 된다. 점프를 한 번 이상 해서 도착할 수 있는 돌을 방문 가능한 돌이라고 하자. 출발 지점인 $s$ 번 돌은 점프를 한 번 이상 한 뒤 다시 밟을 수 있을 때만 방문 가능한 돌에 포함된다.

방문 가능한 돌이 몇 개인지 구하라.

입력

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

둘째 줄에 $A_1, A_2, \dots, A_n$ 이 공백으로 구분되어 주어진다. ( $1 \le A_i \le 100000$ )

셋째 줄에 출발 위치 $s$ 가 주어진다. ( $1 \le s \le n$ )

출력

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

예제8

예제 1
입력
```
5
1 4 2 2 1
3
```
예상 출력
```
4
```
예제 2
입력
```
1
1
1
```
예상 출력
```
0
```
예제 3
입력
```
2
1 1
1
```
예상 출력
```
2
```
예제 4
입력
```
5
1 1 1 1 1
3
```
예상 출력
```
5
```
예제 5
입력
```
6
3 3 3 3 3 3
1
```
예상 출력
```
2
```
예제 6
입력
```
3
100000 100000 100000
2
```
예상 출력
```
0
```
예제 7
입력
```
7
2 2 2 2 2 2 2
1
```
예상 출력
```
4
```
예제 8
입력
```
10
5 3 1 2 4 6 2 8 1 7
4
```
예상 출력
```
9
```