时空限制

1S/512M

题目描述

apiadu 是一位登山爱好者，他计划对某座连绵起伏的山脉进行科学考察。

该山脉的探险路线被等间距地划分为 $n$ 个观测点，第 $i$ 个观测点的高度为 $a_i$。在后续的考察中，apiadu 会根据天气和体能情况，选择不同的连续观测点区间 $[l, r]$ 进行徒步。

为了评估某段路线的起伏程度和徒步难度，apiadu 需要针对每次选择的区间 $[l, r]$，分别统计该区间内部的峰顶和谷底的数量。具体定义如下： 对于区间 $[l, r]$ 内的一个观测点 $i$（需满足 $l \le i - 1 < i < i + 1 \le r$）：

1. 峰顶：若该点高度严格大于前后两个相邻观测点的高度，即 $a_i > a_{i-1}$ 且 $a_i > a_{i+1}$；
2. 谷底：若该点高度严格小于前后两个相邻观测点的高度，即 $a_i < a_{i-1}$ 且 $a_i < a_{i+1}$。

apiadu 总共进行了 $q$ 次路线规划，请你帮他计算出每次规划区间内的峰顶和谷底数量。

格式

输入格式

第一行包含两个整数 $n$ 和 $q$，分别表示观测点的数量和规划路线的次数。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$，表示每个观测点的高度。

接下来 $q$ 行，每行包含两个正整数 $l$ 和 $r$，表示每次规划路线的起止观测点编号。

输出格式

输出 $q$ 行。每行输出两个整数，中间用一个空格隔开，依次表示该规划区间内的峰顶数量和谷底数量。

样例

样例输入 #1

6 4
1 3 2 4 1 5
1 6
1 3
2 5
4 4

样例输出 #1

2 2
1 0
1 1
0 0

数据规模

注意：你只有通过了子任务的所有测试点，才能获得对应子任务的分数。

对于 $100\%$ 的数据，$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 \le r \le n$。