131. Find the Middle Node

Core1000 ms256 MBSolved by 0%

Build the list and print the value of its middle node.

When the list has an even number of nodes there are two middles — print the second one. So a list of four prints the third node.

Print Empty for an empty list.

Constraints - `0 ≤ n ≤ 100000` - `-1000000 ≤ value ≤ 1000000`

Input

The first line contains an integer n, the number of nodes. The second line contains n space-separated integers — the node values from head to tail. The starter code builds the list for you; work on the nodes, not the array.

Output

Print one integer — the value of the middle node. For an even length print the SECOND of the two middle nodes. Print Empty for an empty list.

Input5 1 2 3 4 5

Output3

Notehas an odd length with one clear middle

Input4 1 2 3 4

Output3

Notehas an even length, so the SECOND of the two middles is wanted

Hint 1Approach

Hint 2Approach

Hint 3Pseudocode

Hint 4Full solution