Find the Duplicate Number

You are given an array of n+1 integers where each integer is in the range [1, n] (inclusive). There is exactly one duplicate number in the array, but it could appear more than once. Your task is to find the duplicate number without modifying the array and by using only constant extra space.

To solve the problem, you can employ Floyd’s Tortoise and Hare (Cycle Detection) algorithm. The algorithm works in two phases:

• Phase 1: Find the intersection point of the two runners (slow and fast).
• Phase 2: Find the entrance to the cycle, which will be the duplicate number.

You may refer to the following key formula used in cycle detection: $$x_{i+1} = f(x_i)$$, where f represents the mapping from an index to the next index in the array.

inputFormat

The first line of input contains an integer m, representing the number of elements in the array (which is n+1). The second line contains m space-separated integers representing the array.

outputFormat

Output a single integer, which is the duplicate number found in the array.## sample

5
1 3 4 2 2

2