TULIPNUM  Tulip And Numbers
Little Tulip recently learnt about how to write numbers. So she wrote some numbers in a paper in a line. But she never wrote a number which is less than the prevous one.
Now she want to know how many different numbers are in a given range.
In short, you are given an array of N integers indexed from 1 to N, and q queries, each in the form i j, you have to find the number of distinct integers from index i to j (inclusive).
Input
Input starts with an integer T (≤ 15), denoting the number of test cases.
The first line of a case is a blank line. The next line contains two integers N (1 ≤ N ≤ 10^5), q (1 ≤ q ≤ 10^5). The next line contains N space separated positive integers forming the array. Each of the next q lines will contain a query which is in the form i j (1 ≤ i ≤ j ≤ N).
Output
For each test case, print the case number in a single line. Then for each query you have to print a line containing number of distinct integers from index i to j.
Example
Input: 2 5 3 1 2 2 4 5 1 2 1 5 4 5 3 1 1 1 1 1 3 Output: Case 1: 2 4 2 Case 2: 1
hide comments
akshayvenkat:
20160613 08:28:15
"never wrote a number less than the previous one".. DP :D Last edit: 20160613 08:28:24 

fly_sky12:
20160527 17:20:13
my code took exact 0.2 seconds !!!!


zany:
20160523 10:39:33
Have we to write "Case 1:" before output or just "1" ?


eti goel:
20160522 20:05:01
what is expected time complexity ? my complexity is O(n+q)


naruto09:
20151220 19:23:13
There is no blank line after 1st input..Avoid using sets or vectors in this problem,it will give TLE.. 

MAYANK NARULA:
20151017 23:13:00
Just manage time with care in this easy problem .. 

Advitiya:
20150918 00:05:57
fast i/o AC, else 1 TLE :'( 

vagesh_verma:
20150917 10:19:01
TLE in c++ but AC in c with same code.....!!!! 

ASHUTOSH DWIVEDI:
20150825 22:58:58
Last edit: 20150825 23:04:54 

peeyush taneja:
20150725 22:33:32
nice ques with a good logic 
Added by:  Raihat Zaman Neloy 
Date:  20141014 
Time limit:  0.200s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  Own Problem 