Linked List Compression
You are given an array A of N integers, representing a linked list. For each index i from 0 to N-1, A[i] is the index of the next element. The list starts at index 0. If an index is out of bounds (less than 0 or greater than or equal to N), it signifies the end of the list. The list may contain cycles. Your task is to find the index of the first element that is visited for a second time during a traversal starting from index 0. If the list terminates without revisiting any element, output -1.
Input
The first line contains an integer N (1 <= N <= 200000). The second line contains N integers, A[0], A[1], ..., A[N-1] (-10^9 <= A[i] < 10^9).
Output
Print a single integer: the index of the first element visited twice, or -1 if no element is visited twice.
Constraints
1 <= N <= 200000. -10^9 <= A[i] < 10^9. Indices that are out of bounds (A[i] < 0 or A[i] >= N) represent the end of the list.
Example 1
5 1 2 3 4 0
0
The list is 0 -> 1 -> 2 -> 3 -> 4 -> 0. Index 0 is visited again.
Example 2
7 1 2 3 -1 5 6 4
-1
The list is 0 -> 1 -> 2 -> 3. Index 3 is out of bounds (-1), so the list terminates. No index is repeated.
Hints
# Read the input from stdin and print the answer.
import sys
def main():
data = sys.stdin.read().split()
# your code here
main()
5 1 2 3 4 0
7 1 2 3 -1 5 6 4