G. Music Festival
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

During their stop in Nashville, the UTPC officers decide to attend a country music concert.

At the concert, a group of musicians have lined up, each hoping to perform. However, they are having some trouble deciding on the exact roster, and the organizers of the concert want the officers' help!

To make it easier for the organizer, the officers can only pick some contiguous subarray of the musicians. Each musician has some associated ability, an integer describing how well they can play music. The musicality of a roster of musicians is the median ability in the set. Here, the median of a list of numbers, if written as $$$a_1, a_2, \dots, a_m$$$ in sorted order, is $$$a_{\left\lceil \frac{m + 1}{2} \right\rceil}$$$.

Out of all the possible rosters, the organizers want to find the $$$k$$$-th smallest musicality. Could you help them find this value?

Input

The first line contains two integers $$$n$$$ and $$$k$$$ ($$$1 \leq n \leq 10^5, 1 \leq k \leq 10^{10}$$$) — the number of artists in line and the desired smallest musicality, respectively. It is guaranteed that there are at least $$$k$$$ possible rosters.

The following line contains $$$n$$$ space-separated integers $$$a_1, \dots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$) — the ability of the $$$i$$$-th artist.

Output

Output the $$$k$$$-th smallest musicality possible from all the possible rosters.

Example
Input
4 3
4 2 3 1
Output
2
Note

For the sample:

  • The medians of the size-1 subarrays from left to right are $$$4, 2, 3, 1$$$.
  • The medians of the size-2 subarrays from left to right are $$$4, 3, 3$$$.
  • The medians of the size-3 subarrays from left to right are $$$3, 2$$$.
  • The medians of the size-4 subarray is $$$3$$$.

Putting these in order, we get $$$1, 2, 2, 3, 3, 3, 3, 3, 4, 4$$$ as the possibilities for the medians. Thus, the third index is $$$2$$$.