Find the Middle Element in a Linked List

Given a singly linked list with (n) nodes, your task is to find the middle element of the list. If the list contains an even number of nodes, you should return the (\lceil \frac{n}{2} \rceil)th element (i.e., the second of the two middle elements). For example, in a list with two elements, the middle element is the second element.

You will be given the number of nodes and the node values in order. Construct the linked list accordingly and output the required middle element.

inputFormat

Input is read from stdin. The first line contains an integer (n) representing the number of nodes in the linked list. The second line contains (n) space-separated integers representing the node values in order.

outputFormat

Output to stdout the value of the middle element of the linked list. If the list contains an even number of elements, output the second of the two middle elements.## sample

1
4

4