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
jas.py:
20150626 10:54:20
nice1 

rk:
20150618 22:17:31
so use printf and dont forget that stupid output format Last edit: 20150618 22:18:38 

BRAIN:
20150607 17:25:26
0.19 sec and crazy logic @@ 

@@@:
20150607 16:17:08
AC after 3 TLE's.... :) 

Malfple:
20150330 17:55:55
was trying to use segment tree until i realize the idea is really simple. Good problem 1 TLE~ Last edit: 20150330 17:56:53 

Nebojsa:
20150315 17:23:24
Gave so many WA's because first line of input is NOT A BLANK LINE 

vishal patidar:
20150222 10:44:31
first line of test is not blank line


VISHAL DEEPAK AWATHARE:
20150207 05:07:42
@Lakshman I solved the problem in c++, im trying my best to make input output faster in JAVA, can you point me to some link where i can learn how to make input/output faster? my C++ soultion take time  0.19(can the exactly same program in JAVA take the same or less time) im currently using http://ideone.com/fSroES Last edit: 20150207 05:15:09 

[Lakshman]:
20150206 10:04:53
@Vishal There are two AC in JAVA see this http://www.spoj.com/ranks/TULIPNUM/lang=JAVA 

VISHAL DEEPAK AWATHARE:
20150206 09:21:04
can anyone solve this in JAVA?im getting TLE 
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 