← 返回题目列表

Codeforces · 1514/D

D. 剪切和粘贴

中文机器翻译题面 查看原题

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]$$$。