我有特殊的快排技巧

题目描述

王木木听说大家学习了快速排序，他感觉很兴♂奋，因为他以前上机的时候从来没有手写过排序算法，都是调用sort()函数来排序，嘿嘿！

快排是什么？

对不起，风好大听不清(๑˙ー˙๑)

输入

多组输入数据

第一行为正整数n（1 <= n <= 100000）

接下来n个int范围内的正整数

输出

对于每组数据，输出一行，为这n个数中的的中位数

输入样例

2
1 2
3
2 1 3

输出样例

1
2

Hint

当n为奇数时，输出中间那个

当n为偶数时，输出第n/2个

数据量很大，请使用 scanf & printf 进行输入输出。