Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Limits
1s, 512 MB

Daenerys Targaryen is riding her dragon in a fight against the White Walkers and Wights. There are N Wights standing in a line facing the dragon. Each of them has different level of strength left in them. Daenerys wants to know maximum strength among some consecutive Wights. Write a program to help her in that.

First line of the input contains the number of test cases T (1 <= T <= 100). Then follows input for T test cases. Each test case contains the total number of Wights N (1 <= N <= 10^5) and number of Daenerys’ queries Q (1 <= Q <= 10^5). The next line contains N integers. The i-th integer Ai (1 <= Ai <= 10^5) is the strength of the i-th Wight (1 <= i <= N). The following Q lines will contain two integers L, R (1 <= L <= R <= N). It means Daenerys wants to find maximum strength among Lth Wight to Rth Wight.

For i-th case, print “Case #i:”. In the next Q lines print results of Q queries.

Input | Output |
---|---|

1 5 3 3 1 4 2 5 1 2 1 3 5 5 | Case #1: 3 4 5 |

75% Solution Ratio

YouKnowWhoEarliest,

fire_tornadoFastest, 0.5s

kishore03Lightest, 1.5 MB

wajiulShortest, 734B

Login to submit