## 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月