Limits 1s, 256 MB

You are given an array a1,a2,…,an{a_1, a_2, \dots, a_n}a1,a2,…,an consisting of nnn **distinct** integers and an integer kkk. You can choose any subsequence of size kkk from the array in which the subsequence's elements are in sorted order, lowest to highest. Your task is to calculate the maximum possible median among the subsequence you can choose. If there is no such subsequence, print −1-1−1.

This is a companion discussion topic for the original entry at https://toph.co/p/subsequence-fight