给定一个包含 $n$ 个整数的序列 $a_1, a_2, \dots, a_n$。如果序列的某个连续子段 $a_l, a_{l+1}, \dots, a_{r-1}, a_r$ 满足 $a_l = a_r$，且对于所有整数 $l \le x \le r$，均满足不等式 $a_x \le a_l$，则称该子段为一个“峡谷”（canyon）。特别地，$l = r$ 的情况自动满足该定义，此时该子段也是一个峡谷。峡谷的长度定义为 $r - l$。

你的任务是回答 $m$ 个查询：对于给定的由端点 $l$ 和 $r$ 定义的连续子段 $a_l, a_{l+1}, \dots, a_{r-1}, a_r$，找到该子段内长度最大的峡谷。

输入格式

第一行包含两个整数 $n$ 和 $m$ ($1 \le n, m \le 5 \cdot 10^5$)，分别表示序列的长度和查询的数量。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($-10^9 \le a_i \le 10^9$)。

接下来的 $m$ 行，每行包含两个正整数 $l_i$ 和 $r_i$，描述一个查询 ($1 \le l_i \le r_i \le n$)。

输出格式

对于每个查询，在单独的一行中输出给定子段内峡谷的最大长度。

样例

样例输入 1

8 5
4 3 2 2 3 3 7 3
1 7
6 8
1 3
3 6
1 8

样例输出 1

4
0
0
1
4

说明

在样例测试中，每个查询对应的可能的最大峡谷分别是：$(2, 6)$，$(6, 8)$，$(1, 1)$，$(3, 4)$ 和 $(2, 6)$。