310343: CF1817A. Almost Increasing Subsequence

A. Almost Increasing Subsequencetime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

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.

Input

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$.

Output

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$.

ExampleInput

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

Output

3
4
3
1
4
2
7
1

Note

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$.

题目大意：
一个序列如果不存在三个连续的元素x, y, z，使得x≥y≥z，则称该序列为“几乎递增”的。给定一个数组a[1], a[2], ..., a[n]和q个查询。每个查询包含两个整数l和r，1≤l≤r≤n。对于每个查询，找出子数组a[l], a[l+1], ..., a[r]中最长“几乎递增”子序列的长度。子序列是指可以通过删除零个或多个元素但不改变剩余元素顺序得到的序列。

输入数据格式：
第一行包含两个整数n和q，1≤n, q≤200,000，分别为数组a的长度和查询的数量。
第二行包含n个整数a[1], a[2], ..., a[n]，1≤a[i]≤10^9，为数组a的值。
接下来q行，每行包含两个整数l和r，1≤l≤r≤n，表示查询的子数组a[l], a[l+1], ..., a[r]。

输出数据格式：
对于每个查询，输出一行，包含子数组a[l], a[l+1], ..., a[r]中最长“几乎递增”子序列的长度。

示例：
输入：
9 8
1 2 4 3 3 5 6 2 1
1 3
1 4
2 5
6 6
3 7
7 8
1 8
8 8

输出：
3
4
3
1
4
2
7
1

注意：
在第一个查询中，子数组是a[1], a[2], a[3] = [1,2,4]，整个子数组是几乎递增的，所以答案是3。
在第二个查询中，子数组是a[1], a[2], a[3], a[4] = [1,2,4,3]，整个子数组是几乎递增的，因为没有三个连续的元素满足x≥y≥z。所以答案是4。
在第三个查询中，子数组是a[2], a[3], a[4], a[5] = [2, 4, 3, 3]，整个子数组不是几乎递增的，因为最后三个元素满足4≥3≥3。一个长度为3的几乎递增子序列可以找到（例如取a[2],a[3],a[5] = [2,4,3]）。所以答案是3。题目大意： 一个序列如果不存在三个连续的元素x, y, z，使得x≥y≥z，则称该序列为“几乎递增”的。给定一个数组a[1], a[2], ..., a[n]和q个查询。每个查询包含两个整数l和r，1≤l≤r≤n。对于每个查询，找出子数组a[l], a[l+1], ..., a[r]中最长“几乎递增”子序列的长度。子序列是指可以通过删除零个或多个元素但不改变剩余元素顺序得到的序列。 输入数据格式： 第一行包含两个整数n和q，1≤n, q≤200,000，分别为数组a的长度和查询的数量。 第二行包含n个整数a[1], a[2], ..., a[n]，1≤a[i]≤10^9，为数组a的值。 接下来q行，每行包含两个整数l和r，1≤l≤r≤n，表示查询的子数组a[l], a[l+1], ..., a[r]。 输出数据格式： 对于每个查询，输出一行，包含子数组a[l], a[l+1], ..., a[r]中最长“几乎递增”子序列的长度。 示例： 输入： 9 8 1 2 4 3 3 5 6 2 1 1 3 1 4 2 5 6 6 3 7 7 8 1 8 8 8 输出： 3 4 3 1 4 2 7 1 注意： 在第一个查询中，子数组是a[1], a[2], a[3] = [1,2,4]，整个子数组是几乎递增的，所以答案是3。 在第二个查询中，子数组是a[1], a[2], a[3], a[4] = [1,2,4,3]，整个子数组是几乎递增的，因为没有三个连续的元素满足x≥y≥z。所以答案是4。 在第三个查询中，子数组是a[2], a[3], a[4], a[5] = [2, 4, 3, 3]，整个子数组不是几乎递增的，因为最后三个元素满足4≥3≥3。一个长度为3的几乎递增子序列可以找到（例如取a[2],a[3],a[5] = [2,4,3]）。所以答案是3。