You are given an array A consisting of N elements.
For a subarray of A of length , you have to sort the elements of the subarray in a non-decreasing order. The element at the position is called the median of the subarray. Consider the array and each subarray to be 1 indexed
Write a program to answer Q queries of the following types:
Input format
Output format
For each query, print the median of the subarray.
Constraints
In the 1-st query subarray is . After sorting it will be . The median is 3.
In the 2-nd query subarray is . After sorting it will be . The median is 4.
In the 3-rd query subarray is 5. It's already sorted, so we can easily say that he median is 5.