Given a sequence of integers a1, a2, …, an and q pairs of integers (l1, r1), (l2, r2), …, (lq, rq), find count(l1, r1), count(l2, r2), …, count(lq, rq) where count(i, j) is the number of different integers among a1, a2, …, ai, aj, aj + 1, …, an.
The input consists of several test cases and is terminated by end-of-file. The first line of each test cases contains two integers n and q. The second line contains n integers a1, a2, …, an. The i-th of the following q lines contains two integers li and ri.
For each test case, print q integers which denote the result.