Find smallest start index avoiding left exit

You are given an integer array jump of length n (0-indexed). If you are currently at index i, your next position becomes i + jump[i] (a positive value moves right, a negative value moves left).

Starting from an index s, you repeatedly apply this move rule.

• If you ever reach an index < 0, you have moved out of the left boundary.
• If you reach an index >= n, you have moved out of the array on the right (you may treat this as stopping).
• The process may also loop inside the array.

Return the smallest starting index s such that, during the entire process starting from s, you never move out of the left boundary (i.e., the sequence of visited indices never becomes negative). If no such index exists, return -1.

Implement an algorithm that runs in O(n) time if possible.

Find Smallest Start Index Avoiding Left Exit

You are given an integer array jump of length n (0-indexed). From index i, your next position is i + jump[i]. A positive value moves right, a negative value moves left, and 0 keeps you on the same index.\n\nStarting from an index s, repeatedly apply this rule:\n- If the next index becomes < 0, you have exited through the left boundary.\n- If the next index becomes >= n, you have exited on the right and the process stops.\n- The process may also loop forever inside the array.\n\nReturn the smallest starting index s such that the process starting from s never exits through the left boundary. Exiting on the right or looping inside the array is allowed. If no such starting index exists, return -1.

Constraints

• 0 <= n <= 200000
• -10^9 <= jump[i] <= 10^9
• An O(n) solution is expected.

Examples

Example 1

Input: ([-1, -1, -1, -1, 2],)
Output: 4

Explanation: Indices 0 through 3 eventually move to -1. Starting at 4 jumps to 6, which exits on the right, so the answer is 4.

Example 2

Input: ([0, -2, 1],)
Output: 0

Explanation: Index 0 jumps to itself forever, which is allowed. Therefore the smallest valid start is 0.

Hints

1. Think of each index as a node with exactly one outgoing edge to i + jump[i].
2. If a walk revisits a node already seen in the same exploration, you found an internal cycle, which is safe because it can never suddenly exit left.