哲学家的沉思

题号：NC222283
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

非正常人类研究中心的哲学家牛拉底鲁曾有一句名言：“人一次也不能踏进同一条河流”，除此之外他还喜欢将连续的一段划分为若干片段。你作为中心的一名员工，为了照顾牛拉底鲁的生活起居，不得不陪他玩这样的一个游戏。

这个游戏的过程如下：牛拉底鲁会给你 $n$ 个数字，第 $i$ 个数字为 $a[i]$ 。接下来他会进行 $q$ 次询问，每次询问将给出两个数字 $l$ 与 $r$ ，要你把 $[l,r]$ 区间划分为若干个片段 $[l_{1},r_{1}],[l_{2},r_{2}],...,[l_{k},r_{k}]$ 。要求对于任意一个片段 $[l_{i},r_{i}]$ ， $a[l_{i}]$ 为这个片段中的最大值。

牛拉底鲁想要最小化片段的数量，因此对于每次询问，请你回答出 $k$ 的最小值。

输入描述:

第一行两个正整数 $n$ , $q$ ，其中 $n\leq 10^{5}$ , $q\leq 10^{5}$ 。

第二行 $n$ 个正整数 $a[i]$ ， $a[i]\leq 10^{9}$ 。

接下来 $q$ 行，每行两个正整数 $l$ 与 $r$ ，其中 $l\leq r \leq n$ 。

输出描述:

对每次询问输出 $k$ 的最小值。

示例1

输入

复制

输出

复制

2
2

说明

对于询问1，可以把[3,5]划分为[3,4],[5,5]。
对于询问2，可以把[1,2]划分为[1,1],[2,2]。

示例2

输入

复制

输出

复制

1
2

说明

对于询问1，可以把[1,2]划分为[1,2]。
对于询问2，可以把[1,3]划分为[1,2],[3,3]。