Module: Mo algorithm


Problem

1 /4


The number of different on the segment

Theory Click to read/hide

Error

Problem

You are given an array of integers A of length n.
It is necessary to answer m queries of the form "report the number of different numbers of a subsegment of array A from the element with index l to the element with index r" (both boundaries of the subsegment are included, the array is numbered from one).

Input:
The first line contains two numbers: n - the number of array elements and m - the number of requests (1 <= n, m <= 105).
The second line contains n integers Ai - array elements (0 <= Ai <= 106).
Then there are m lines, each containing two numbers l and r - the boundaries of the subsegment for each query (1 <= l <= r <= n).

Output:
In a single line print m space-separated numbers - for each query, the number of different numbers on the corresponding subsegment.

Example:
 
Input Output
7 5
1 3 1 2 2 4 1
1 3
4 5
37
24
77
2 1 3 3 1