该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Description

给定一个长度为 $n$ 的正整数序列 $a$ ，设序列 $a$ 的第 $i$ 个元素为 $a_i$ .

对于给定的 $l,r(1 \le l \le r \le n)$，求 $a_l$ 到 $a_r$ 中的第 $k$ 小的元素.

Input Format

输入包含两行，第一行包含空格隔开的四个整数 .

$n,l,r,k(1 \le n \le 10^5, 1 \le l \le r \le n, 1 \le k \le r - l + 1)$

第二行包含 $n$ 个空格隔开的正整数，表示序列 $a(1 \le a_i \le 10^9)$.

Output Format

输出包含一个整数，表示 $a_l$ 到 $a_r$ 中的第 $k$ 小的元素.

5 2 4 2
1 2 3 4 5​

3