Description

小沈想向自己倾慕已久的女神小计告白，可是又怕被拒绝。为此很是苦恼，他的朋友对他说你没有勇气尝试，永远都不会知道结果有多么的惊喜。最终，小沈还是怀着忐忑的心去表白。

事情的结果很是惊喜啊！小计并没有拒绝，但是小计给他出了一道难题。题目是这样描述的：有两个玩家在玩一个游戏，一开始的时候，在黑板上写下n个整数。每轮游戏中玩家从中挑选一个数并删除。直到最后只剩下最后一个数。第一个玩家想最后一个数尽可能的小，而第二个玩家却想剩的数尽可能的大。每轮游戏从第一个玩家开始。问每轮最后剩的数是多少？现在小沈要为他终生的幸福去奋斗。那么聪明的你能帮助小沈赢得美人归吗？

Format

Input

第一行输入n（1<=n<=1000）,表示黑板上有多少个整数。

第二行输入n个整数a1,a2,...an(1<=ai<=106)。

Output

输出每轮最后剩的数。

Samples

3
1 2 2

2

Hint