Harmonic Triplets

3.8

6 votes
Binary Search, Medium, Range Queries, Segment Trees, Sets
Problem

You are given an array A. A triplet is said to be a Harmonic triplet if it satisfies the following conditions :

  • i<j<k
  • A[i]A[j]A[k]


You have to find the harmonic triplet with the maximum value of A[i]×A[j]×A[k].
You are given q queries, where in each query you are given jth index and you have to find the harmonic triplet with value at jth 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 jth 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

  • 1T5
  • 1N,Q105
  • 1A[i]105
  • 1jN

Note
Use fast I/O techniques.

Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation
  • 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.
Editor Image

?