http://e-maxx.ru/algo/rmq_linear

I think any generic RMQ algorithm like sparse table is a huge overkill in this problem.

You should take advantage of the fact that K ≤ len(Q) ≤ K·2. Split A into blocks of size K. Each query will be covered by 1 ≤ n ≤ 3 blocks.

This is How i solved it :

since it is given that for every query the range of query ( r — l + 1 ) is greater than or equal to K or less than equal to 2 * K . So we can use this fact in out solution . Now lets divide the array into blocks of size K . So for a query , we will have to traverse O( ( r — l + 1 ) / K ) blocks . so thats O(1) . Great , now we just have to see how we should make the blocks of size K . So now lets keep 2 arrays : prefix[N] , suffix[N] where prefix[i] will store the minimum of all numbers from start of the block to which i belongs till i and similarly suffix[i] will store the minimum of all elements from end of the block to which i belongs till i . This can be calculated in O(N) time . Now when we get a query from l to r . in worst case we will have 3 blocks to check , for the first block , just check suffix[l] , for the last block just check prefix[r] and incase another block exists in the middle which is completely in range , check the minimum of the whole block using prefix[end_of_block] or suffix[start_of_block] . and take the minimum of these 3 numbers , thats your answer .

Here is the c++ implementation solution

PS. the solution looks huge but its actually not , i used a lot of lines of my code just for the array and query generation .