该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

山路观景

题目描述

有一条山路，共有 $n$ 个位置，第 $i$ 个位置的高度为 $a_i$。

现在有 $q$ 次询问，每次询问给出一个区间 $[l,r]$。

对于一次询问，一个位置 $i$ 被称为这个区间内的一个“观景点”，需要满足：

1. $l < i < r$；
2. $a_i > a_{i-1}$；
3. $a_i > a_{i+1}$。

也就是说，观景点必须是区间内部的一个局部山峰，区间的左右端点不能作为观景点。

请你对于每次询问，输出区间 $[l,r]$ 中观景点的数量。

输入格式

第一行输入两个整数 $n,q$，表示位置数量和询问次数。

第二行输入 $n$ 个整数 $a_1,a_2,\dots,a_n$，表示每个位置的高度。

接下来 $q$ 行，每行输入两个整数 $l,r$，表示一次询问的区间。

数据范围

对于所有测试数据，满足：

• $3 \le n \le 2 \times 10^5$；
• $1 \le q \le 2 \times 10^5$；
• $1 \le a_i \le 10^9$；
• $1 \le l < r \le n$。

输出格式

对于每次询问，输出一行一个整数，表示答案。

输入输出样例 #1

输入 #1

8 5
1 3 2 5 4 6 1 2
1 8
1 3
2 5
4 7
6 8

输出 #1

3
1
1
1
0

说明/提示

原序列为：

1 3 2 5 4 6 1 2

其中满足局部山峰的位置有：

• 位置 $2$，因为 $3>1$ 且 $3>2$；
• 位置 $4$，因为 $5>2$ 且 $5>4$；
• 位置 $6$，因为 $6>4$ 且 $6>1$。

所以对于询问 $[1,8]$，答案为 $3$。

对于询问 $[6,8]$，虽然位置 $6$ 是整个序列中的局部山峰，但是它是区间 $[6,8]$ 的左端点，不能作为这个区间内的观景点，所以答案为 $0$。