You are given an array A. A triplet is said to be a Harmonic triplet if it satisfies the following conditions :
- \(i \lt j \lt k\)
- \(A[i] \le A[j] \ge A[k]\)
You have to find the \(harmonic\) \( triplet\) with the maximum value of \(A[i] \times A[j] \times A[k]\).
You are given q queries, where in each query you are given \(j^{th}\) index and you have to find the \(harmonic\) \(triplet\) with value at \(j^{th}\) index which has maximum product.
Note
If there are no elements to the left or right of j which satisfy the given conditions, answer for the given index will be 0.
Input format
- The first line contains single integer T denoting the number of test cases. T test cases follow.
- The first line of each test case consists of two space-separated integers \(N, Q\) denoting size of the array and number of the queries respectively.
- Next line contains N spaced integers denoting contents of the array.
- The next Q lines contain values of \(j^{th}\) index for which you have to find harmonic triplet with maximum product.
Output format
- For each test case, for each query print a single line consisting of the maximum possible product for that query.
Constraints
- \(1 \le T \le 5\)
- \(1 \le N,Q \le 10^5\)
- \(1 \le A[i] \le 10^5\)
- \(1 \le j \le N\)
Note
Use fast I/O techniques.
- Maximum Harmonic Triplet at index 5 can be made by using A[2]*A[5]*A[6] or by using A[4]*A[5]*A[6] which has value 6
- Maximum Harmonic Triplet at index 3 can be made by using A[2]*A[3]*A[5] which has value 42
- Maximum Harmonic Triplet at index 6 can't be made as there is no k > j available.
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor
Login to unlock the editorial
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor