CF1817A.Almost Increasing Subsequence

A sequence is almost-increasing if it does not contain three consecutive elements $x, y, z$ such that $x\ge y\ge z$.

You are given an array $a_1, a_2, \dots, a_n$ and $q$ queries.

Each query consists of two integers $1\le l\le r\le n$. For each query, find the length of the longest almost-increasing subsequence of the subarray $a_l, a_{l+1}, \dots, a_r$.

A subsequence is a sequence that can be derived from the given sequence by deleting zero or more elements without changing the order of the remaining elements.

如果一个序列不包含三个连续元素 $x, y, z$ 满足 $x\ge y\ge z$，则称该序列为近似递增序列（almost-increasing）。

给定一个数组 $a_1, a_2, \dots, a_n$ 和 $q$ 个查询。

每个查询包含两个整数 $1\le l\le r\le n$。对于每个查询，请找出子数组 $a_l, a_{l+1}, \dots, a_r$ 的最长近似递增子序列的长度。

子序列是指从原序列中删除零个或多个元素（不改变剩余元素的相对顺序）所得到的序列。

The first line of input contains two integers, $n$ and $q$ ($1 \leq n, q \leq 200\,000$) — the length of the array $a$ and the number of queries.

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \leq a_i \leq 10^9$) — the values of the array $a$.

Each of the next $q$ lines contains the description of a query. Each line contains two integers $l$ and $r$ ($1 \leq l \leq r \leq n$) — the query is about the subarray $a_l, a_{l+1}, \dots, a_r$.

输入的第一行包含两个整数 $n$ 和 $q$（$1 \leq n, q \leq 200\,000$）——分别表示数组 $a$ 的长度和查询次数。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \leq a_i \leq 10^9$）——表示数组 $a$ 的各元素值。

接下来的 $q$ 行，每行描述一个查询。每行包含两个整数 $l$ 和 $r$（$1 \leq l \leq r \leq n$）——该查询针对子数组 $a_l, a_{l+1}, \dots, a_r$。

For each of the $q$ queries, print a line containing the length of the longest almost-increasing subsequence of the subarray $a_l, a_{l+1}, \dots, a_r$.

对于每个查询，输出一行，包含子数组 $a_l, a_{l+1}, \dots, a_r$ 的最长近似递增子序列的长度。

In the first query, the subarray is $a_1, a_2, a_3 = [1,2,4]$. The whole subarray is almost-increasing, so the answer is $3$.

In the second query, the subarray is $a_1, a_2, a_3,a_4 = [1,2,4,3]$. The whole subarray is a almost-increasing, because there are no three consecutive elements such that $x \geq y \geq z$. So the answer is $4$.

In the third query, the subarray is $a_2, a_3, a_4, a_5 = [2, 4, 3, 3]$. The whole subarray is not almost-increasing, because the last three elements satisfy $4 \geq 3 \geq 3$. An almost-increasing subsequence of length $3$ can be found (for example taking $a_2,a_3,a_5 = [2,4,3]$ ). So the answer is $3$.

在第一个查询中，子数组为 $a_1, a_2, a_3 = [1,2,4]$。整个子数组是几乎递增的，因此答案为 $3$。

在第二个查询中，子数组为 $a_1, a_2, a_3,a_4 = [1,2,4,3]$。整个子数组是几乎递增的，因为不存在三个连续元素满足 $x \geq y \geq z$。因此答案为 $4$。

在第三个查询中，子数组为 $a_2, a_3, a_4, a_5 = [2, 4, 3, 3]$。整个子数组不是几乎递增的，因为最后三个元素满足 $4 \geq 3 \geq 3$。但可以找到一个长度为 $3$ 的几乎递增子序列（例如取 $a_2,a_3,a_5 = [2,4,3]$）。因此答案为 $3$。