Maximum Window Median

You are given an array of integers and a list of queries. For each query, which specifies a window size \(w\), consider every contiguous subarray (window) of length \(w\) in the array. The median of a window is defined as the element at index \(\lfloor (w-1)/2 \rfloor\) when the window is sorted in non-decreasing order. Your task is to compute, for each query, the maximum median across all windows of the specified size.

Note: For a window of even length, the median is the lower of the two middle values. For example, if a window is [2, 1] then after sorting it becomes [1,2] and its median is 1.

Example:

Input array: [2, 1, 5, 7, 2, 0, 5]
Queries: [1, 2, 3]
For window size 1: All windows are single elements, maximum median is 7.
For window size 2: Windows are [2,1] (median 1), [1,5] (median 1), [5,7] (median 5), [7,2] (median 2), [2,0] (median 0), [0,5] (median 0); maximum median is 5.
For window size 3: Windows are [2,1,5] (median 2), [1,5,7] (median 5), [5,7,2] (median 5), [7,2,0] (median 2), [2,0,5] (median 2); maximum median is 5.
Thus, output: [7, 5, 5].

</p>

inputFormat

The input is read from standard input (stdin) and has the following format:

N
a1 a2 ... aN
Q
w1 w2 ... wQ

Where:

• N is the number of elements in the array.
• a1, a2, ..., aN are the elements of the array.
• Q is the number of queries.
• w1, w2, ..., wQ are the window sizes for the queries.

outputFormat

For each query, output the maximum window median value. The results for all queries should be printed on a single line, separated by spaces. The output is written to standard output (stdout).

## sample

7
2 1 5 7 2 0 5
3
1 2 3

7 5 5