A team of archaeologists found an antic antique. It was fresco in a huge alcove near Fountain For Triangles(FFT in short.) On this fresco it had drawn n triangles marked with numbers. They had also found a scroll with some pair of numbers flip-flopping on it. It seemed to be a fully secured captcha. Soon the team members realized that before they took a photograph for the fresco, they needed to answer the question from the captcha. The questions were simple, the only thing you need to answer is within the range from L-th triangle to R-th triangle, how many distinct numbers are there?
The screen on the scroll was in the state of flux (although fluxx is fun, but in this case, answering the question seems need an ability of foreknowledge.) Please answer all the question that scroll would prompt out for the archaeologists.
First line contains an integer T(1<=T<=100) indicating the number of test cases.
For each test case, first line contains an integer n (1<=n<=105), second line contain n integers a1, a2, …, an (1<=ai<=106). Third line contains an integer q(1<=q<=105). Each of the next q lines contains two integers L, R (1<=L<=R<=n) indicating the queries.
For each test case, please output the answer for each query.
1 5 1 1 2 1 3 3 1 5 2 4 3 5
3 2 3
Migrated from old NTUJ.
Shik and Tmt
| No. | Testdata Range | Score |
|---|