# 小Y的线段树

预估时间限制：1.5 秒。内存限制：512 MB。

实际时限以标准程序在目标环境的最慢用例中位时间乘以 $10$ ，按 $0.5$ 秒向上取整。参考环境见[评测说明](../../../docs/评测环境与性能.md)。

本题采用倍率十，为支持逐条回答询问的倍增实现保留至少两倍实测余量。各程序耗时见[测量记录](../../../docs/benchmark-R25.json)。

## 背景故事

> “这是什么newbee操作？”

小Y不是死宅，他喜欢玩碧蓝，小学时还是体育生，所以他出了一道线段树题。

他有一个长度为 $N$ 的序列。他会告诉你序列的长度和每个位置的元素，却说“不会给你这个序列”。接下来有 $M$ 次询问：将区间 $[l,r]$ 中的元素从左到右依次放入一个初始为空的严格单调递减栈，最终栈的大小是多少？

## 形式化问题描述

给定长度为 $N$ 的整数序列 $a_1,\ldots,a_N$ 和 $M$ 个询问。每个询问给出 $[l,r]$ ，独立从空栈开始，按 $a_l,a_{l+1},\ldots,a_r$ 的顺序处理每个元素 $v$ ：

1. 只要栈非空且栈顶值不大于 $v$ ，就弹出栈顶。
2. 将 $v$ 压入栈。

因此，栈中元素从底到顶严格递减，相等的旧元素也会弹出。输出每次询问处理结束后的栈大小。询问之间不保留栈，也不修改序列。

## 输入格式

第一行两个整数 $N,M$ .第二行 $N$ 个整数 $a_1,\ldots,a_N$ .接下来 $M$ 行，每行两个整数 $l,r$ .

## 输出格式

输出 $M$ 行，第 $i$ 行一个整数，表示第 $i$ 个询问的答案。

## 样例

### 样例 1

### 输入

```text
5 4
5 3 3 4 2
1 5
2 4
2 3
5 5
```

### 输出

```text
3
1
1
1
```

### 样例 2

### 输入

```text
2 1
1 2
1 2
```

### 输出

```text
1
```

### 样例 3

### 输入

```text
3 2
9 7 5
1 3
2 3
```

### 输出

```text
3
2
```

## 样例解释

第一组的四个最终栈从底到顶分别为 $(5,4,2)$ 、$(4)$ 、$(3)$ 、$(2)$ .相等的两个三只留下后读入的一个。第二组中新值二会弹出一。第三组两个区间本身都严格递减。

![区间处理时栈的变化](assets/example.zh.svg)

## 数据范围与保证

$1\le N,M\le5\times10^5$ , $0\le a_i\le10^9$ , $1\le l\le r\le N$ .

| 分值比例 | 额外条件 |
| --- | --- |
| 100% | 无额外条件 |