An Amazon hiring team is reviewing the scores of KaTeX can only parse string typed expression candidates.
The score of candidate KaTeX can only parse string typed expression is KaTeX can only parse string typed expression.
The team wants to choose exactly KaTeX can only parse string typed expression candidates as a subsequence. A subsequence is formed by deleting zero or more elements without changing the order of the remaining elements.
For every chosen subsequence of size KaTeX can only parse string typed expression, its median is the element at position KaTeX can only parse string typed expression after sorting that subsequence in non-decreasing order using 1-based indexing.
Your task is to find the minimum possible median and the maximum possible median among all subsequences of size KaTeX can only parse string typed expression.
The first line contains two integers KaTeX can only parse string typed expression and KaTeX can only parse string typed expression — the number of candidates and the size of the subsequence to choose.
The second line contains KaTeX can only parse string typed expression integers KaTeX can only parse string typed expression — the candidate scores.
Print two integers — the minimum possible median and the maximum possible median among all subsequences of size KaTeX can only parse string typed expression.
Input
6 3
8 1 5 2 9 42 8After sorting the array, we get KaTeX can only parse string typed expression.
For KaTeX can only parse string typed expression, the median position is KaTeX can only parse string typed expression.
To get the minimum possible median, choose the smallest KaTeX can only parse string typed expression values: KaTeX can only parse string typed expression. The median is KaTeX can only parse string typed expression.
To get the maximum possible median, choose the largest KaTeX can only parse string typed expression values: KaTeX can only parse string typed expression. The median is KaTeX can only parse string typed expression.
So the answer is KaTeX can only parse string typed expression and KaTeX can only parse string typed expression.
Example 2:
Input
5 4
7 7 7 7 77 7Every subsequence of size KaTeX can only parse string typed expression has the same values, so both medians are KaTeX can only parse string typed expression.
Example 3:
Input
4 1
10 -3 6 2-3 10When KaTeX can only parse string typed expression, the median of a subsequence is its only element. The minimum possible median is the smallest array value and the maximum possible median is the largest array value.