P12598 参数要吉祥

扶苏是一个大型语言模型。她共有 $n$ 个参数，依次为 $a_1, a_2, \dots a_n$。现在，你要和她进行 $q$ 次交互。扶苏有先进的混合专家模型（MoE）技术，每轮交互你都会给定一个区间 $[l, r]$，扶苏只有 $a_l, a_{l + 1}, \dots a_r$ 这些参数会被激活。 对于整数 $x$，我们定义其吉祥程度为在一组激活的参数里出现次数为 $x$ 的数的种类数，记为 $c(x)$。对于每次交互，你要找到一个 $x$ 使 $x \times c(x)$ 最大，输出 $x \times c(x)$。 例如，对于一组参数 $[1,1,2,2,33,33,444,444,444]$，则有 $1,2,33$ 这三种数出现了 $2$ 次，取 $x = 2$，得到 $x \times c(x) = 6$。

第一行是两个整数，表示参数个数 $n$ 和交互次数 $q$。 第二行有 $n$ 个整数，表示 $a_1, a_2, \dots a_n$。 接下来 $q$ 行，每行两个整数，表示一次交互激活的参数区间 $[l, r]$。

对每次交互，输出一行一个整数，表示最大的 $x \times c(x)$。

### 数据规模与约定 |测试点编号| $n,q\leq$|特殊约定| |:-: | :-: | :-: | | $1 \sim 4$ | $100$ | 无 | | $5 \sim 9$ | $10^3$ | 无 | | $10 \sim 15$ | $3 \times 10^4$ | 无| | $16 \sim 21$ | $2 \times 10^5$ | 每个数出现次数均不超过 $100$| | $22 \sim 25$ | $2 \times 10^5$ | 无 | 对全部的测试数据，保证 $1 \leq n,a_i, q \leq 2 \times 10^5$，$1 \leq l \leq r \leq n$。