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 ith person is denoted by an integer Ai not exceeding M.
Chef decided to have some fun. At first, he forms K groups of people. The ith group consists of all the people numbered from Li to Ri. 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.
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 A1, A2, ..., AN denoting the growth of people. Then the ith line of the next K lines contains two space-separated integers Li, Ri, denoting the ith group.
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 ≤ Ai ≤ M
- 1 ≤ Li ≤ Ri ≤ N
Subtask 1: 20 points
- 1 ≤ N, M, K ≤ 1000 = 103
Subtask 2: 80 points
- 1 ≤ N, M, K ≤ 100000 = 105
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
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 A5 = 5 and A6 = 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 A3 = 6, A4 = 6 and A5 = 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 A1 = A7 = 4. So the answer is |7 − 1| = 6.
|Tags||gomelfk, march15, medium, sqrt-decomp|
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, 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, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.