Consider an -integer sequence, . We perform a query on by using an integer, , to calculate the result of the following expression:
In other words, if we let , then you need to calculate .
Given and queries, return a list of answers to each query.
Example
The first query uses all of the subarrays of length : . The maxima of the subarrays are . The minimum of these is .
The second query uses all of the subarrays of length : . The maxima of the subarrays are . The minimum of these is .
Return .
Function Description
Complete the solve function below.
solve has the following parameter(s):
- int arr[n]: an array of integers
- int queries[q]: the lengths of subarrays to query
Returns
- int[q]: the answers to each query
Input Format
The first line consists of two space-separated integers, and .
The second line consists of space-separated integers, the elements of .
Each of the subsequent lines contains a single integer denoting the value of for that query.
Constraints
Sample Input 0
5 5
33 11 44 11 55
1
2
3
4
5
Sample Output 0
11
33
44
44
55
Explanation 0
For , the answer is
For , the answer is
For , the answer is
For , the answer is
For , the answer is
Sample Input 1
5 5
1 2 3 4 5
1
2
3
4
5
Sample Output 1
1
2
3
4
5
Explanation 1
For each query, the "prefix" has the least maximum value among the consecutive subsequences of the same size.