Mock CCC '19 Contest 1 J5 - One-way Hopscotch
You are playing hopscotch on a one-indexed array \(a\) of \(N\) integers. You can choose to start at some index \(j\) (which is undecided). Your goal is to reach index \(N\). This game of hopscotch is strange. At index \(i\), it is already defined where you must hop to. At index \(i\), you must hop to index \(i + a_i\).
You want to find out, for how many starting indices \(j\) \((1 \le j \le N)\) will you be able to reach index \(N\)?
The first line will contain the integer \(N\) \((1 \le N \le 10^5)\), the number of elements.
The second line will contain \(N\) integers, \(a_1, a_2, \ldots, a_N\) \((1 \le a_i \le 10^3)\).
Output the number of starting indices \(j\) \((1 \le j \le N)\) where you will be able to reach index \(N\).
For 3/15 of the points, \(N \le 10^3, a_i \le 10\).
For an additional 4/15 of the points, \(a_i \le 10\).
6 5 2 2 2 3 1
Explanation For Sample
You will be able to reach index \(N=6\) when starting at indices \(1, 2, 4,\) or \(6\).