Migrated from Lutece 2532 大佬集中营

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

一群大佬坐在班上的第一排，学渣们都喜欢请一部分大佬去帮他写作业，每个大佬都有一个非常擅长的学科，我们用序号 $1\sim n$ 表示 $n$ 个不同的学科，用一个数组 $a_i$ 表示从左到右第 $i$ 个位置上的大佬擅长 $a_i$ 编号的学科。

但是大佬并不总是有空，比如有些大佬今天可能在摸鱼，有些大佬可能今天生病了……但有意思的是，有空的大佬总是坐在一起的，也就是说不管任何时候，有空的大佬总是位于第 $l$ 个位置到第 $r$ 个位置的连续位置上。

不过班上的学渣实在是太多了，你可以认为有正无穷个学渣，不是每个学渣都能享受大佬的恩惠。而学渣又非常贪婪，只要大佬有空，他就会想尽办法去邀请大佬来帮他写作业，不同学科的大佬负责帮学渣写不同学科的作业。

一般来讲学渣会叫尽可能多的各个学科的大佬来帮忙，但是同一个学科的大佬太多的话可能会起冲突，因为大佬们会开始争论谁的答案更标准，谁的解释更有说服力。假设某个学渣叫来了 $k$ 个大佬来帮他写作业，那么这 $k$ 个大佬中擅长同一个学科的大佬数量一定不能超过 $\lceil \frac k2\rceil$，$\lceil x\rceil$ 指的是不小于 $x$ 的最小整数，比如 $\lceil 2.5\rceil=3,\lceil 2\rceil=2$。

现在给定大佬的数量 $n$，以及每个大佬擅长的学科，并且告知每天有空的大佬所在的位置区间 $[l,r]$，你需要回答这些大佬最少能分配给几个学渣。

Input

第一行输入两个整数 $n,q\ (1\le n,q\le 3\times 10^5)$，分别代表大佬数量和接下来 $q$ 天的询问。

第二行输入 $n$ 个整数 $a_1,a_2,a_3,\ldots ,a_n\ (1\le a_i\le 3\times 10^5)$，代表从左到右第 $i$ 个大佬擅长的学科。

接下来 $q$ 行每行给定两个整数 $l,r\ (1\le l\le r\le n)$，代表有空的大佬所在的区间是 $[l,r]$。

Output

对于每天的询问你需要输出区间 $[l,r]$ 内的大佬最少能分配的学渣数目。

Samples

5 2
1 1 1 4 5
1 5
1 4

1
2

4 1
1 1 1 1
1 4

4

Resources

2021 UESTC ICPC Training for Data Structures