Module: Mo algorithm

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 <= 10⁵).
The second line contains n integers A_i - array elements (0 <= A_i <= 10⁶).
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