#P1997. faebdc 的烦恼

faebdc 的烦恼

题目背景

鸟哥(faebdc)自从虐暴 NOIP2013 以来依然勤奋学习,每天上各种 OJ 刷题,各种比赛更是不在话下。但这天他遇到了一点小小的麻烦:在一届“Orz 鸟哥杯”上,题目是在是太多了!鸟哥看得头晕眼花,他需要你的帮助。

题目描述

这场比赛共有 nn 道题,每道题都有一个难度值 aia_i,由于 wangxz 神犇已经提前帮助鸟哥将这些难度值升序排列,所以鸟哥并不想知道哪些题难度低或者高,他只想知道在某些题目 al,al+1,,ara_l,a_{l+1},\ldots,a_r中,出现最多的难度值出现的次数。

你的任务就是对于鸟哥的每一次询问 (l,r)(l, r),告诉他在从 ala_lara_r(rl+1)(r-l+1) 道题之中,出现最多的难度值出现的次数(询问共有 qq 次)。

如果你成功地帮助了鸟哥,鸟哥将会带你通过省选。

输入格式

每个测试点有且仅有一组测试数据。

第一行有两个整数,分别表示题目的数量 nn 和询问的次数 qq

第二行有 nn 个整数,第 ii 个整数 aia_i 表示第 ii 道题的难度。

接下来 qq 行,每行两个整数 l,rl, r,表示一次询问。

输出格式

对于每组询问,输出一行一个整数表示答案。

9 1
1 1 1 2 2 3 3 4 4
3 8
2

提示

数据规模与约定

对于全部的测试点,保证 1n1051 \leq n \leq 10^51q2×1051 \leq q \leq 2\times 10^5105ai105-10^5 \leq a_i \leq 10^51lrn1 \leq l \leq r \leq n