Triplets Min CodeChef Solution July 2023

Problem

You are given an integer array $�$ of size $�$.
A triplet array is defined as the collection of $\min ({�}_{�},{�}_{�},{�}_{�})$ for all triplets $(�,�,�)$, where $1\le �<�<�\le �$.

You are given $�$ queries of the following type:

• Given an integer $�$, return the value of ${�}^{�ℎ}$ smallest element in the triplet array.

Input Format

• The first line of input will contain a single integer $�$, denoting the number of test cases.
• Each test case consists of multiple lines of input.
  • The first line of each test case contains two space-separated integers $�$ and $�$ — the size of array $�$ and the number of queries, respectively.
  • The second line of each test case contains $�$ space-separated integers ${�}_1,{�}_2,\dots ,{�}_{�}$.
  • The following $�$ lines describe the queries. Each of these lines contain a single positive integer $�$.

Output Format

For each query, print a single line containing the ${�}^{�ℎ}$ smallest element in the triplet array.

Explanation:

Test case 1: Here, all elements of triplet array are equal to $3$.

Test case 2: The sorted triplet array is $[1,1,1,2]$.