A conveyor belt carries a singly linked list of package codes, front to back. Find the MIDDLE package. If the belt holds an even number of packages (so there are two middle packages), report the one that is FARTHER from the front. Print that package's code.
Input format
Line 1: an integer n — the number of packages.
Line 2: n space-separated integers — the package codes, front to back.
Output format
A single integer: the code of the middle package as defined above.
Constraints
- 1 ≤ n ≤ 100000
- -1000000000 ≤ package code ≤ 1000000000