Time Limit: 9000/4500 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others) Total Submission(s): 1654 Accepted Submission(s): 420
Problem Description Mr. Frog has an integer sequence of length n, which can be denoted asa1,a2,⋯,an There are m queries.
In thei−th query, you are given two integersli andri. Consider the subsequenceali,ali+1,ali+2,⋯,ari.
We can denote the positions(the positions according to the original sequence) where an integer appears first in this subsequence asp(i)1,p(i)2,⋯,p(i)ki (in ascending order, i.e.,p(i)1<p(i)2<⋯<p(i)ki).
Note that ki is the number of different integers in this subsequence. You should output p(i)⌈ki2⌉for the i-th query.
Input In the first line of input, there is an integer T(T≤2) denoting the number of test cases.
Each test case starts with two integers n (n≤2×10^5) and m (m≤2×10^5). There are n integers in the next line, which indicate the integers in the sequence(i.e.,a1,a2,⋯,an,0≤ai≤2×105).
There are two integersli andri in the followingm lines.
However, Mr. Frog thought that this problem was too young too simple so he became angry. He modified each query to$ l‘_i,r‘_i(1≤l‘i≤n,1≤r‘i≤n). $As a result, the problem became more exciting.
We can denote the answers asans1,ans2,⋯,ansm. Note that for each test caseans0=0.
You can get the correct input li,ri from what you read (we denote them asl‘i,r‘i)by the following formula: li=min(l‘i+ansi−1)modn+1,(r‘i+ansi−1)modn+1
ri=max(l‘i+ansi−1)modn+1,(r‘i+ansi−1)modn+1
Output You should output one single line for each test case.
For each test case, output one line “Case #x:p1,p2,⋯,pm”, wherex is the case number (starting from 1) andp1,p2,⋯,pm is the answer.