题目描述

给你一个长度为 $n$ 的数列 $a_1, a_2, \ldots, a_n$ 以及 $q$ 次询问。

每次询问给你两个整数 $l_i$ 和 $r_i$，你需要回答出下标区间 $[l_i, r_i]$ 范围内（即 $a_{l_i}, a_{l_i + 1}, \ldots, a_{r_i}$）中出现次数最多的那个（或那些）数的出现次数。

输入格式

第一行，两个整数 $n$ 和 $q$，以一个空格分隔（$1 \le n \le 10^5, 1 \le q \le 2 \cdot 10^5$）。

第二行，$n$ 个整数 $a_1, a_2, \ldots, a_n(-10^5 \le a_i \le 10^5)$。

接下来 $q$ 行，每行包含两个整数 $l_i$ 和 $r_i$，以一个空格分隔，表示一次询问（$1 \le l_i \le r_i \le n$）。

输出格式

对于每次询问的 $l_i$ 和 $r_i$，输出一行，包含一个整数，表示下标区间 $[l_i, r_i]$ 范围内（即 $a_{l_i}, a_{l_i + 1}, \ldots, a_{r_i}$）中出现次数最多的那个（或那些）数的出现次数。

样例

9 3
1 1 1 2 2 3 3 4 4
3 8
1 4
5 6

2
3
1