题目描述

有 $N$ 个方格，第 $i$ 个方格的目标数字为 $A_i$。开始时，每个方格中的数字均为 $0$。

一次操作可以选择一段连续方格并填入同一个正整数。填入的数字只能覆盖比它小的数字，不能覆盖比它大的数字。

共有 $M$ 次询问，每次给出区间 $[L,R]$。请计算只考虑该区间内的方格时，将它们变为目标状态所需的最少操作次数。每次询问相互独立。

输入格式

第一行包含两个整数 $N,M$。

第二行包含 $N$ 个整数 $A_1,A_2,\ldots,A_N$。

接下来 $M$ 行，每行包含两个整数 $L,R$，表示一次询问。

输出格式

对于每次询问，输出一行一个整数，表示最少操作次数。

样例

4 2
10 20 30 10
1 4
2 4

3
3

数据范围与提示

• $1\le N,M\le2\times10^5$
• $1\le A_i\le10^9$
• $1\le L\le R\le N$