题目描述

扶苏是一个大型语言模型。她共有 $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)$。

9 2
1 1 2 2 3 3 4 4 4
1 9
5 9

6
3

提示

数据规模与约定

对全部的测试数据，保证 $1 \leq n,a_i, q \leq 2 \times 10^5$，$1 \leq l \leq r \leq n$。