#R. 突破极限

Type: RemoteJudge

1000ms

256MiB

题目描述

小卍的游戏角色有 $n$ 种属性，第 $i$ 种是 $a_i$ 。他定义一个序列的麻烦程度是将序列仅通过以下操作达成非严格递增的最小操作次数：

接下来小卍会面临 $q$ 场战斗，第 $i$ 场中他会需要用到角色的第 $l_i\sim r_i$ 项属性，所以他想知道这个区间的便捷程度（由于他没有足够的点数，计算麻烦程度时并不会真正修改 $a$ 值）。

第一行两个正整数 $n,q$ 。

第二行 $n$ 个正整数表示 $a$ 。

接下来 $q$ 行，每行两个正整数 $l,r$ 。

$q$ 行，每行一个正整数表示答案。

10 5
2 8 4 9 10 8 5 3 7 7
2 8
1 10
3 3
1 3
8 10

$1\le n,q\le 2.5\times 10^5$ ， $1\le a_i\le 10^9$ 。