C. Johnny English Strikes Again
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

After successfully forming groups once Johny English became famous for group formation. Now the Prime Minister wants to test if Johny English is actually good at group formation or if it was just a lucky shot. There are $$$n$$$ people standing in a line. The person at $$$i^{th}$$$ belongs to the country $$$c_i$$$. The Prime Minister asked Johny English to divide these people into groups following these conditions:

  1. Each person must be in some group
  2. Each group can consist of one or two people
  3. No two people from the same country can be in the same group
  4. A VIP can't be in the same group with a non-VIP
Before starting the group formation Johny English will ask you some queries. In the $$$i^{th}$$$ query he will give you two integers $$$l_i$$$ and $$$r_i$$$. For each query, you have to tell him the minimum number of groups he can divide those n people into if and only if people from $$$l_i^{th}$$$ position to $$$r_i^{th}$$$ position are VIPs.
Input

The first line of the Input contains two integers $$$n$$$ $$$(1\le n \le 10^6)$$$ and $$$q$$$ $$$(1\le q \le 10^5)$$$ denoting the number of people. The next line contains $$$n$$$ integers denoting $$$c_i$$$ $$$(1 \le c_i \le 10^5)$$$. $$$i^{th}$$$ of the next $$$q$$$ lines contains two integers $$$l_i$$$ and $$$r_i$$$ $$$1 \le l_i \le r_i \le n$$$.

Output

For each query print one integer in a single line denoting the answer to the query.

Example
Input
6 9
2 3 3 1 1 1
3 5
4 5
1 5
1 1
1 6
3 5
3 4
3 3
1 6
Output
4
4
4
4
3
4
3
4
3