310351: CF1818C. Almost Increasing Subsequence

C. 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个查询。每个查询包含两个整数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]中最长的“几乎递增”子序列的长度。题目大意： 一个序列如果不存在三个连续的元素x, y, z使得x≥y≥z，则称该序列为“几乎递增”的。给定一个数组a[1], a[2], ..., a[n]和q个查询。每个查询包含两个整数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]中最长的“几乎递增”子序列的长度。