猪猪取数

问题描述

猪猪面前有一个神奇的盒子，开始是空的。

接下来他会依次把 $n$ 个数字放进盒子。全部放完后，猪猪会恰好进行 $k$ 次取数操作,首先会给出一个取数规则$t$:

• 若 $t=0$：每次都从盒子里取出当前最小的数字并丢掉；
• 若 $t=1$：每次都从盒子里取出当前最大的数字并丢掉。

问：完成这 $k$ 次取数后，盒子里在当前取数规则下现在应当被取出的那个数字是什么？

输入格式

• 第一行：整数 $t$，选择规则（$0$ 取最小，$1$ 取最大）
• 第二行：整数 $n$，表示放入的数字个数
• 第三行：$n$ 个整数 $a_1,\dots,a_n$
• 第四行：整数 $k$，表示取数次数（全部放完后一次性做）

输出格式

输出一个整数，为完成 $k$ 次取数后，此时应当被取出的数字。

样例

1
6
5 1 4 2 3 6
2

4

解释：$t=1$ 表示每次取最大。依次取走的是 6、5，剩下 $[1,2,3,4]$，此时下一次应取最大为 4，故答案 4。

数据范围

$1<k<n\le 2\times 10^5$，$1\le a_i\le 10^9$，$t\in\{0,1\}$。