Chef and Problems

All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian.
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:
Please help Chef to have fun.
Input
There is only one test case in one test file.
The first line of input contains three spaceseparated integers N, M and K, denoting the number of people, the maximum growth and number of groups respectively. The second line contains N spaceseparated integers A_{1}, A_{2}, ..., A_{N} denoting the growth of people. Then the i^{th} line of the next K lines contains two spaceseparated 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^{3}
Subtask 2: 80 points
 1 ≤ N, M, K ≤ 100000 = 10^{5}
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} = 5 and A_{6} = 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_{3} = 6, A_{4} = 6 and A_{5} = 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_{1} = A_{7} = 4. So the answer is 7 − 1 = 6.
Author:  gomelfk 
Tester:  laycurse 
Editorial  http://discuss.codechef.com/problems/QCHEF 
Tags  gomelfk, march15, medium, sqrtdecomp 
Date Added:  30102014 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, ERL, TCL, PERL6, TEXT, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions