Chef was invited to the party of N people numbered from 1 to N. Chef knows the growth of all the people, i.e. he knows the growth of the i^th person is denoted by an integer A_i not exceeding M.

Chef decided to have some fun. At first, he forms K groups of people. The i^th group consists of all the people numbered from L_i to R_i. Groups may overlap too.

For each group, Chef wants to know the following information: the maximum difference between the numberings of two people having same growth. Formally, Chef wants to know the following:

max{|x - y| : L_i = x, y = R_i and A_x = A_y}

Please help Chef to have fun.

Input

There is only one test case in one test file.

The first line of input contains three space-separated integers N, M and K, denoting the number of people, the maximum growth and number of groups respectively. The second line contains N space-separated integers A₁, A₂, ..., A_N denoting the growth of people. Then the i^th line of the next K lines contains two space-separated integers L_i, R_i, denoting the i^th group.

Output

For each group, output the integer denoting the maximum difference between numbering of two people having same growth in a single line.

Constraints and Subtasks

• 1 = A_i = M
• 1 = L_i = R_i = N

 

Subtask 1: 20 points

• 1 = N, M, K = 1000 = 10³

 

Subtask 2: 80 points

• 1 = N, M, K = 100000 = 10⁵

Example

Input: 7 7 5 4 5 6 6 5 7 4 6 6 5 6 3 5 3 7 1 7 Output: 0 0 1 1 6

Explanation

Group 1. There is only one person in the group. Thus the maximum difference of numbers should be 0.

Group 2. There are two persons in the group. Their growth are A₅ = 5 and A₆ = 7. Thus there is no pair of persons who have the same growth. Thus the answer for this group will also be 0.

Group 3. There are three persons in the group. Their growth are A₃ = 6, A₄ = 6 and A₅ = 5. Here person 3 and person 4 has the same growth. Thus the answer is |4 - 3| = 1.

Group 4. There are more persons than the group 3. But they has different growth, other than person 3 and person 4.Thus the answer is also |4 - 3| = 1.

Group 5. This group contains all the people, and person 1 and person 7 has the same growth A₁ = A₇ = 4. So the answer is |7 - 1| = 6.