CF1514D.Cut and Stick

Baby Ehab has a piece of Cut and Stick with an array $a$ of length $n$ written on it. He plans to grab a pair of scissors and do the following to it:

• pick a range $(l, r)$ and cut out every element $a_l$, $a_{l + 1}$, ..., $a_r$ in this range;
• stick some of the elements together in the same order they were in the array;
• end up with multiple pieces, where every piece contains some of the elements and every element belongs to some piece.

More formally, he partitions the sequence $a_l$, $a_{l + 1}$, ..., $a_r$ into subsequences. He thinks a partitioning is beautiful if for every piece (subsequence) it holds that, if it has length $x$, then no value occurs strictly more than $\lceil \frac{x}{2} \rceil$ times in it.

He didn't pick a range yet, so he's wondering: for $q$ ranges $(l, r)$, what is the minimum number of pieces he needs to partition the elements $a_l$, $a_{l + 1}$, ..., $a_r$ into so that the partitioning is beautiful.

A sequence $b$ is a subsequence of an array $a$ if $b$ can be obtained from $a$ by deleting some (possibly zero) elements. Note that it does not have to be contiguous.

Baby Ehab 有一张“剪切与粘贴”（Cut and Stick）卡片，上面写有一个长度为 $n$ 的数组 $a$。他打算拿起一把剪刀，对这张卡片执行以下操作：

• 选定一个区间 $(l, r)$，并剪下该区间内所有元素 $a_l$, $a_{l + 1}$, ..., $a_r$；
• 将其中一部分元素按其在原数组中的相同顺序粘贴在一起；
• 最终得到若干个片段，每个片段包含若干元素，且每个元素恰好属于某一个片段。

更形式化地说，他将序列 $a_l$, $a_{l + 1}$, ..., $a_r$ 划分为若干个子序列。他称一个划分是优美的（beautiful），当且仅当：对每个片段（即每个子序列），若其长度为 $x$，则其中任意数值的出现次数均不超过 $\lceil \frac{x}{2} \rceil$ 次。

他尚未选定具体区间，因此他想知道：对于给定的 $q$ 个查询区间 $(l, r)$，将元素 $a_l$, $a_{l + 1}$, ..., $a_r$ 划分为优美划分时，所需的最少片段数是多少？

注意：序列 $b$ 是数组 $a$ 的一个子序列，当且仅当 $b$ 可通过从 $a$ 中删除若干（可能为零）个元素得到。注意子序列不必连续。

The first line contains two integers $n$ and $q$ ($1 \le n,q \le 3 \cdot 10^5$) — the length of the array $a$ and the number of queries.

The second line contains $n$ integers $a_1$, $a_2$, ..., $a_{n}$ ($1 \le a_i \le n$) — the elements of the array $a$.

Each of the next $q$ lines contains two integers $l$ and $r$ ($1 \le l \le r \le n$) — the range of this query.

第一行包含两个整数 $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$）—— 表示该次查询的区间范围。

For each query, print the minimum number of subsequences you need to partition this range into so that the partitioning is beautiful. We can prove such partitioning always exists.

对于每个查询，请输出将该区间划分为若干子序列所需的最少数量，使得该划分是“优美的”。我们可以证明这样的划分总是存在的。

In the first query, you can just put the whole array in one subsequence, since its length is $6$, and no value occurs more than $3$ times in it.

In the second query, the elements of the query range are $[3,2,3,3]$. You can't put them all in one subsequence, since its length is $4$, and $3$ occurs more than $2$ times. However, you can partition it into two subsequences: $[3]$ and $[2,3,3]$.

在第一个查询中，你可以将整个数组放入一个子序列中，因为其长度为 $6$，且其中没有任何数值出现次数超过 $3$ 次。

在第二个查询中，查询区间内的元素为 $[3,2,3,3]$。你不能将它们全部放入一个子序列中，因为该子序列长度为 $4$，而数值 $3$ 的出现次数超过了 $2$ 次。然而，你可以将其划分为两个子序列：$[3]$ 和 $[2,3,3]$。