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
DOT:
20180822 09:44:57
Easy question. Once you make certain observations from the input being sorted, you can solve in O(1) per query. 

jmr99:
20180717 21:51:21
same problem here https://www.spoj.com/problems/DQUERY/


Simes:
20180517 09:02:57
I think the input may be malformed. In Pascal, I got WA with readln, and AC with read. 

madhavgaba:
20170102 12:53:04
1 dimensional dp and 200th came easy.....all credits @pulkitgulati:) Last edit: 20170102 12:54:38 

Piyush Kumar:
20160720 08:30:35
O! One of those problems where the author doesn't care if you have an optimal solution. He wants to test whether you can take input and print numbers faster _ 

ov3rk1ll:
20160702 07:07:00
Use fast io


dwij28:
20160627 11:45:09
Whenever a problem setter sets a question with strict time limit, they must take care that the I/O format is not weird or at least there is no ambiguity in the I/O format. One needs to appreciate that fast input completely relies on the input format and creating troubles in that does not judge someone's coding abilities. 

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" ?

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 