提示: 欢迎访问OurACM平台。
Problem 1862 QueryProblem

Accept: 108    Submit: 280
Time Limit: 2000 mSec    Memory Limit : 32768 KB

Problem Description


There are N numbers (non-negative integers) in a circle. Now your task is quite simple, just tell me the largest number between L and R.
The Figure 1 is a sample of five integers in a circle. (marked with their index, but not their exact value.)
Figure 1.

The Figure 2,3 show how we count the number.

Figure 2.


Figure 3.

Input

There are no more than 10 test cases;

For each case, the first line contains only one integer N, indicates the size of the circle.

The following one line contains N non-negative integers where Mi indicates the i-th integers whose index is i. (1 <= N <= 1000, 1 <= i <= N, 0 <= Mi <= 10^9)

Then one line contains Q indicates the number of querys. (1 <= Q <= 10^5)

Then the next Q lines, each line contains only two integers indicate L and R (1 <= L,R <= N)

Output

For each case, please output “Case #index:” in a single line, here index is the case index starts from one.

For each query just output a single line indicates the largest number between L and R.

Output a blank line after each case.

Sample Input

2 3 8 3 1 1 1 2 2 1 1 9 1 1 1

Sample Output

Case #1: 3 8 8 Case #2: 9

Hint

Huge Input, please “scanf” to avoid time limit exceed.

Source

FOJ有奖月赛-2009年11月

Submit  Back  Status  Discuss