链接: https://cses.fi/problemset/task/3304

板块: Range Queries

时限: 1.00 s ｜ 内存: 512 MB

题目描述

有 $n$ 栋建筑排成一排，从左到右编号为 $1,2,\dots,n$。你站在第一栋建筑的左侧。如果一栋建筑比它左边所有建筑都高，你就能看见它。

你的任务是处理 $q$ 个查询：如果世界上只存在区间 $[a, b]$ 内的建筑，你能看见多少栋建筑？

输入

第一行包含两个整数 $n$ 和 $q$：分别表示建筑数量和查询数量。

第二行包含 $n$ 个整数 $h_1, h_2, \dots, h_n$：各建筑的高度。

最后有 $q$ 行描述查询。每行包含两个整数 $a$ 和 $b$。

输出

对每个查询输出一个整数：可见建筑的数量。

数据范围

$1 \le n \le 10^5$ $1 \le q \le 2 \cdot 10^5$ $1 \le h_i \le 10^9$ $1 \le a \le b \le n$

样例输入

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

样例输出

1
3
1