Jump Jump 2

Interview

Time limit2sMemory limit512 MB

Summary

Given a walk that adds or subtracts A_i at each step, count the stones reachable from start s, excluding s unless a cycle returns to it.

Level: Medium5 of 10
Topics: Graph, BFS, Implementation, Math
Solved: No attempts yet

Problem

Youngwoo the frog is on a stone bridge made of $n$ stones in a row. The stones are numbered $1$ to $n$ from the left, and stone $i$ has a single number $A_i$ written on it. From stone $i$ Youngwoo can jump exactly $A_i$ stones to the left or to the right, landing on stone $i - A_i$ or on stone $i + A_i$ . He cannot jump to a position numbered below $1$ or above $n$ .

Youngwoo starts on stone $s$ . There is no limit on the number of jumps, and he may land on the same stone more than once. Call a stone visitable if Youngwoo can land on it after one or more jumps. The starting stone $s$ is visitable only when he can land back on it after at least one jump.

Count the visitable stones.

Input

The first line contains the number of stones $n$ ( $1 \le n \le 100000$ ).

The second line contains $A_1, A_2, \dots, A_n$ , separated by spaces ( $1 \le A_i \le 100000$ ).

The third line contains the starting position $s$ ( $1 \le s \le n$ ).

Output

Print the number of visitable stones on the first line.

Examples8

Example 1
Input
```
5
1 4 2 2 1
3
```
Expected output
```
4
```
Example 2
Input
```
1
1
1
```
Expected output
```
0
```
Example 3
Input
```
2
1 1
1
```
Expected output
```
2
```
Example 4
Input
```
5
1 1 1 1 1
3
```
Expected output
```
5
```
Example 5
Input
```
6
3 3 3 3 3 3
1
```
Expected output
```
2
```
Example 6
Input
```
3
100000 100000 100000
2
```
Expected output
```
0
```
Example 7
Input
```
7
2 2 2 2 2 2 2
1
```
Expected output
```
4
```
Example 8
Input
```
10
5 3 1 2 4 6 2 8 1 7
4
```
Expected output
```
9
```