题目描述

一个研究团队正在研究象形文字序列的一些性质。他们将每个象形文字的复杂程度表示成一个正整数，并且没有两个象形文字被表示成相同的数。

对于一个长度为 $n$、下标从 $1$ 开始的序列 $A$，定义如下概念：

1. $A$ 被称为一个排列，当且仅当 $1,2,\ldots,n$ 在 $A$ 中分别恰好出现一次。
2. 序列 $B$ 被称为 $A$ 的子序列，当且仅当 $B$ 可以通过删除 $A$ 中若干个元素得到，删除元素的数量可以为 $0$。
3. $A$ 的区间 $[l,r]$ 指序列 $A_l,A_{l+1},\ldots,A_r$。

研究人员想知道：对于给定排列 $A$ 的若干个区间 $[l_i,r_i]$，该区间内最长上升子序列的长度是多少。

输入格式

第一行包含两个正整数 $n,q$，分别表示排列大小和询问个数。

第二行包含 $n$ 个正整数 $a_i$，表示排列 $A$。

接下来 $q$ 行，每行包含两个正整数 $l_i,r_i$，表示一次查询的区间。

输出格式

输出 $q$ 行，每行输出一个正整数，表示对应区间的最长上升子序列长度。

数据范围

对于所有数据，保证：

• $1\le n\le 10^5$；
• $1\le q\le 10^6$；
• $1\le a_i\le n$；
• $A$ 是一个排列。

子任务

样例

输入

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

输出

3
2
1
3
2