题目描述

专诸一剑刺死吴王僚后，自己也被卫兵乱刀砍死。酒席上顿时大乱，公子光记录了每位宾客的反应类型，形成一个长度为 $n$ 的整数序列 $a_1, a_2, \dots, a_n$。

现在有 $q$ 组询问，每次询问给你两个整数 $l, r$，问区间 $a_l \sim a_r$ 中出现次数最多的反应类型出现了多少次。

输入格式

第一行两个整数 $n, q$（$1 \le n, q \le 10^4$）。

第二行 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le 10^6$）。

接下来 $q$ 行，每行两个整数 $l, r$（$1 \le l \le r \le n$），表示一组询问。

输出格式

输出 $q$ 行，每行一个整数，表示答案。

7 3
3 3 3 1 1 2 2
1 5
2 4
1 7

3
2
3