Baby Ehab 有一块 Cut and Stick,上面写着一个长度为 $$$n$$$ 的数组 $$$a$$$。他计划抓起一把剪刀并对其进行以下操作:
- 选择一个范围 $$$(l, r)$$$ 并删除该范围内的每个元素 $$$a_l$$$, $$$a_{l + 1}$$$, ..., $$$a_r$$$ ;
- 将一些元素按照它们在数组中的顺序粘在一起;
- 最终得到多个片段,其中每个片段都包含一些元素,并且每个元素都属于某个片段。
更正式地说,他将序列 $$$a_l$$$, $$$a_{l + 1}$$$, ..., $$$a_r$$$ 划分为子序列。他认为,如果对于每个片段(子序列)来说,如果它的长度为 $$$x$$$,那么其中出现的值严格不会超过 $$$\lceil \frac{x}{2} \rceil$$$ 次,那么这种划分就是美丽的。
他还没有选择一个范围,所以他想知道:对于 $$$q$$$ 范围 $$$(l, r)$$$,他需要将元素 $$$a_l$$$、$$$a_{l + 1}$$$、...、$$$a_r$$$ 划分为最少的块数,这样划分才美观。
如果可以通过删除一些(可能为零)元素从 $$$a$$$ 获得 $$$b$$$,则序列 $$$b$$$ 是数组 $$$a$$$ 的子序列。请注意,它不必是连续的。
输入
第一行包含两个整数 $$$n$$$ 和 $$$q$$$ ($$$1 \le n,q \le 3 \cdot 10^5$$$) - 数组 $$$a$$$ 的长度和查询数量。
第二行包含 $$$n$$$ 整数 $$$a_1$$$, $$$a_2$$$, ..., $$$a_{n}$$$ ($$$1 \le a_i \le n$$$) — 数组 $$$a$$$ 的元素。
接下来的 $$$q$$$ 行包含两个整数 $$$l$$$ 和 $$$r$$$ ($$$1 \le l \le r \le n$$$) — 此查询的范围。
输出
对于每个查询,打印您需要将此范围划分为的最小子序列数,以便划分美观。我们可以证明这样的划分总是存在的。
示例
输入 #1
6 2 1 3 2 3 3 2 1 6 2 5
输出 #1
1 2
注意
在第一个查询中,您可以将整个数组放入一个子序列中,因为它的长度为 $$$6$$$,并且其中没有任何值出现超过 $$$3$$$ 次。
在第二个查询中,查询范围的元素为$$$[3,2,3,3]$$$。您不能将它们全部放在一个子序列中,因为它的长度为 $$$4$$$,而 $$$3$$$ 出现的次数超过 $$$2$$$ 次。但是,您可以将其划分为两个子序列:$$$[3]$$$ 和 $$$[2,3,3]$$$。