Count Groups

You are given the numeric label of each cable. Within each independent query range, only two cables with the same label can form a group, and each cable can be used at most once. Find the maximum number of groups that can be formed in the range. What follows is this site's standard input/output protocol.

输入格式

The first line contains n and q; the second line contains n labels; each of the next q lines contains l and r, a 1-based closed range. Queries are independent of each other.

输出格式

Output the q answers in input order, separated by spaces. Each answer is the sum, over all labels, of the label's number of occurrences in the range divided by 2 and rounded down.

样例 1

输入：

4 2
2 3 4 2
1 4
3 4

输出：

1 0

样例 2

输入：

4 1
2 2 2 2
1 4

输出：

2

样例 3

输入：

1 1
1000000000
1 1

输出：

0

样例说明

Use Mo's algorithm to move the range endpoints, maintaining the frequency of each label and the number of groups formed.