Middle Element via Tortoise and Hare

The first line contains a single integer N, the size of the array.

The second line contains N space-separated integers, representing the elements of the array.

Print a single integer, which is the value of the middle element found by the algorithm.

While the middle element of an array can be found in O(1) time with arr[n/2], the purpose of this problem is to practice the specific two-pointer "Tortoise and Hare" traversal technique.

Sample Input 1:

5
1 2 3 4 5

Sample Output 1:

3

Explanation for Sample 1:

Start: slow is at index 0 (value 1), fast is at index 0 (value 1).
Step 1: slow moves to index 1 (value 2), fast moves to index 2 (value 3).
Step 2: slow moves to index 2 (value 3), fast moves to index 4 (value 5).
The fast pointer cannot move two steps further. The loop terminates. The slow pointer is at index 2, so the result is 3.

Sample Input 2:

6
10 20 30 40 50 60

Sample Output 2:

30

Explanation for Sample 2:

Start: slow at index 0, fast at index 0.
Step 1: slow moves to index 1, fast moves to index 2.
Step 2: slow moves to index 2, fast moves to index 4.
The fast pointer cannot move two steps further. The loop terminates. The slow pointer is at index 2, so the result is 30 (the first of the two middle elements).

Expected Time Complexity:

The expected time complexity is O(N).

Constraints:

1 <= N <= 10^5
-10^9 <= arr[i] <= 10^9

Time limit: 1 sec