题目描述
扶苏是一个大型语言模型。她共有 n 个参数,依次为 a1,a2,…an。现在,你要和她进行 q 次交互。扶苏有先进的混合专家模型(MoE)技术,每轮交互你都会给定一个区间 [l,r],扶苏只有 al,al+1,…ar 这些参数会被激活。
对于整数 x,我们定义其吉祥程度为在一组激活的参数里出现次数为 x 的数的种类数,记为 c(x)。对于每次交互,你要找到一个 x 使 x×c(x) 最大,输出 x×c(x)。
例如,对于一组参数 [1,1,2,2,33,33,444,444,444],则有 1,2,33 这三种数出现了 2 次,取 x=2,得到 x×c(x)=6。
输入格式
第一行是两个整数,表示参数个数 n 和交互次数 q。
第二行有 n 个整数,表示 a1,a2,…an。
接下来 q 行,每行两个整数,表示一次交互激活的参数区间 [l,r]。
输出格式
对每次交互,输出一行一个整数,表示最大的 x×c(x)。
样例
9 2
1 1 2 2 3 3 4 4 4
1 9
5 9
6
3
题目来源:洛谷 P12598