题目描述

给定一个头结点为 head 的非空单链表，返回链表的中间结点。

如果有两个中间结点，则返回第二个中间结点。

输入格式

第一行一个正整数 n，表示链表的长度。

第二行 n 个整数，表示链表中每个节点的值，按从前往后的顺序给出。

输出格式

输出一行一个整数，表示中间节点的值。

样例

5
1 2 3 4 5

3

6
1 2 3 4 5 6

4

样例解释

样例1中：链表为 [1, 2, 3, 4, 5]，中间节点是 3，输出3。

样例2中：链表为 [1, 2, 3, 4, 5, 6]，有两个中间节点（3和4），根据题目要求，返回第二个中间节点，即4，输出4。

数据范围