One day, Nafu was whining a lot to his roommate Pika to buy Nafu some food. Nafu is famously known as a blackhole for his ability to eat ‘almost’ any amount of food, he just loves to eat! Having no other option to shut Nafu up, Pika took him to a restaurant where N dishes of food are sold.
In the restaurant, all the dishes are indexed from 1 to N and the amount of food in each dish is written in the menu. Now, knowing that Nafu wants to eat only K amount of food, Pika gave Nafu the option to pick only one dish within L’th dish to R’th dish (inclusive). Nafu will surely pick the dish with amount of food closest to K, doesn’t matter if it has more food or less food than K as he has the ability to eat any amount of food without wasting anything! Pika wants to know beforehand which dish Nafu will choose if he tells Nafu to choose one from all dishes with index L to R, and if Nafu wants to eat K amount of food. Help him!
Formally, you will be given an array A of N numbers, where A[i] is the amount of food in i’th dish and 1 <= i <= N.
You will then be given M queries on the form of L R K, for each query, you have to print i such that |A[i] - K| is minimum and L <= i <= R. If multiple such i exists, print the minimum one.
Input starts with an integer T (T <= 5), denoting the number of test cases.
Each case starts with an integer N (1 <= N <= 105), number of dishes. Then the next line will contain N integers where i’th integer A[i] (0 <= A[i] <= 109) represents the amount of food in i-th dish.
Then an integer Q (1 <= Q <= 105) will be given, denoting the number of queries. Then each next Q lines will give 3 integers L R K (1 <= L <= R <= N, 0 <= K <= 109).
For each query L R K, in a single line, print the dish index Nafu will choose from L’th to R’th dishes if he wants to eat K amount of food. Read problem description for more details.
Do this for each test case.
| Input | Output |
|---|---|
1 5 1 7 6 3 6 3 1 3 7 1 4 5 4 5 4 | 2 3 4 |
Dataset is huge. Use faster I/O.