在这片大地，流传着 $Elo$ 的不败传说。

然而 $Howarli$ 不屑一顾，对着 $Elo$ 说："砍死你就完事儿了"。

$Howarli$ 轻而易举就获胜了，但是正当 $Howarli$ 回味自己创下的传说的时候...

死去的 $Elo$ 突然开始攻击祂！

死去的 $Elo$ 突然开始攻击祂！

死去的 $Elo$ 突然开始攻击祂！

$Elo$ 复活了！

$Elo$ 死后，祂的灵魂被标号分成了不相同的 $n$ 个灵魂碎片，散落在世界各地，从左到右可以用一个排列 $p_i$ 表示。

因为被 $Howarli$ 削弱了，如今 $Elo$ 复活的条件非常苛刻：

1、祂只能选择一段区间 $[l,r]$，尝试使用这段区间内的灵魂碎片进行不完全复活

2、因为灵魂的连续性，灵魂需要按标号顺序拼接，例如存在灵魂碎片集合 {$1,6,4,5,2$}, 那么可以拼出 $12$ 与 $456$ 两种极大灵魂片段，长度分别为 $2$ 和 $3$

3、$Elo$ 想尽力完整复活，所以祂会从中选出最长的灵魂片段，其余灵魂片段则完全丢弃。

不败的 $Elo$ 无数次地尝试复活，但是死去的祂没有脑子，祂想知道自己选出的区间 $[l,r]$ 内，能拼接出的最长灵魂片段是多长，你能帮帮祂吗？

第一行两个整数 $n,m(1\leq n,m\leq 50000)$，分别表示排列长度与询问次数。

接下来一行 $n$ 个整数，表示排列 $p_i(1\leq p_i \leq n, 且 p_i 两两不同)$。

接下来 $m$ 行，每行两个整数 $l,r$，描述一组询问，表示 $Elo$ 选择的区间 $[l,r]$。

对于每组询问，输出一行一个整数，表示 $Elo$ 能拼接出的最长灵魂片段长度。

对于询问 $[1,4]$，$p_2,p_4,p_1$ 组成最长的灵魂片段 $123$

对于询问 $[5,8]$，$p_8,p_5,p_7$ 组成最长的灵魂片段 $456$

对于询问 $[1,7]$，$p_5,p_7,p_3,p_6$ 组成最长的灵魂片段 $5678$