Find the Middle of a Linked List

You are given a singly linked list with n nodes. Your task is to find the middle node of the list. If the linked list contains an even number of nodes, you should return the second middle node.

For example, consider a linked list with values [1, 2, 3, 4, 5, 6]. Even though there are two middle nodes (3 and 4), you are required to return 4.

In mathematical terms, if the linked list has n nodes, then:

• If n is odd, the middle node is at position $\frac{n+1}{2}$.
• If n is even, the middle node is at position $\frac{n}{2} + 1$.

You must read input from stdin and output the answer to stdout.

inputFormat

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 values of the nodes in order.

outputFormat

Output a single integer, which is the value of the middle node as defined in the problem.

## sample

5
1 2 3 4 5

3

</p>