Even Frequency Types

You are given an array of n positive integers (each not exceeding some constant c) and m queries. Each query provides two indices l and r indicating a contiguous segment of the array. Your task is to determine how many distinct numbers in this segment appear a positive even number of times.

More formally, for a query [l, r], let freq(x) be the number of occurrences of number x in the subarray a[l...r]. You need to count the number of distinct x such that freq(x) is even and greater than 0.

It is guaranteed that the input will be such that a solution which processes each query independently will suffice.

inputFormat

The first line contains two integers n and m separated by a space.

The second line contains n positive integers a₁, a₂, ..., a_n, each not greater than c.

The following m lines each contain two integers l and r (1-indexed) describing a query.

outputFormat

For each query, print a single integer on a new line representing the number of distinct numbers in the subarray a[l...r] that appear a positive even number of times.

sample

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

2
1
1