Find the Middle Element in a Singly Linked List

You are given a singly linked list represented by an array of integers. Your task is to determine the middle element of the list. If the list contains (n) elements (indexed from 0 to (n-1)), then the middle element is defined as the element at index (\lfloor n/2 \rfloor). In the case of an even-length list, output the data of the second middle node.

For example, if the list is [1, 2, 3, 4, 5], the middle element is 3. If the list is [1, 2, 3, 4, 5, 6], the middle element is 4.

The input is given through standard input (stdin) and the result must be printed to standard output (stdout).

inputFormat

The first line of input contains an integer (n) — the number of nodes in the linked list. The second line contains (n) space-separated integers denoting the data values of the nodes.

outputFormat

Output a single integer, which is the data of the middle node. For an even-length list, output the data of the second middle node.## sample

5
1 2 3 4 5

3