seuOJ432 - 数数

• 题目类型：传统
• 输入文件：标准输入流
• 输出文件：标准输出流
• 时间限制：1000 ms
• 空间限制：256 MiB
• 题目标签：冬季, 校赛, 决赛, 2022

题目描述

有一个长度为 $n$ 的序列和 $q$ 次询问，每次询问序列中有多少区间（不包括 $[l,r]$ ）的最大值等于区间 $[l,r]$ 的最大值。

输入格式

第一行两个正整数 $n,q(1\leq n,q\leq 100000)$。

第二行 $n$ 个正整数 $a_i(1\leq a_i\leq n)$ 表示序列。

接下来 $q$ 行每行两个正整数 $l,r(1\le l\le r\le n)$。

输出格式

$q$ 行，表示每组询问的答案。

样例

样例输入:

8 3
1 4 7 7 4 4 1 1
3 4
5 8
1 1

样例输出:

22
8
3