Count Numbers Appearing Exactly Twice in a Range

You are given an array of N natural numbers. Then you are asked Q queries. For each query, you need to determine the count of distinct natural numbers that appear exactly twice in the subarray defined by the range [L, R].

The problem can be formally described as follows:

Given an array A of length N where each element is a natural number, answer Q queries. Each query is specified by two integers L and R (with 1 ≤ L ≤ R ≤ N). For each query, compute the number of distinct values x such that the frequency of x in the segment A[L...R] is exactly 2.

In mathematical notation, for each query, find the count of numbers x satisfying:

Note: The array is 1-indexed.

inputFormat

The first line contains two integers N and Q separated by a space.

The second line contains N natural numbers representing the array.

Each of the following Q lines contains two integers L and R representing a query.

outputFormat

For each query, output a single line containing one integer — the number of distinct natural numbers in the subarray [L, R] that appear exactly twice.

sample

5 3
1 2 3 2 1
1 5
2 4
3 3

2
1
0