Mock CCC '19 Contest 1 J5 - One-way Hopscotch

View as PDF

Submit solution

Points: 7 (partial)
Time limit: 2.0s
Memory limit: 64M

Problem type

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\)?

Input Specification

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 Specification

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\).

Sample Input

5 2 2 2 3 1

Sample Output


Explanation For Sample

You will be able to reach index \(N=6\) when starting at indices \(1, 2, 4,\) or \(6\).