Almost Increasing Subsequence
Contest: Codeforces Round 869 (Div. 1)
Difficulty rating: 1500
Tags: binary search, data structures, greedy

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

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

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

Example input:
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

Example output:
3
4
3
1
4
2
7
1

Editorial:
It is not obvious how the condition in the statement for an almost-increasing subsequence can be turned into a fast data structure that can support queries. So instead of tackling the problem head on, let's try to make an upperbound for how many elements can be in the maximum length almost-increasing subsequence.
Assume you're given a query about the subarray of the original array $$$[a_l, a_{l+1}, \dots, a_r]$$$. Let's partition this array into decreasing subarrays. This means everytime when $$$a_i < a_{i+1}$$$ we place a cut between $$$a_i$$$ and $$$a_{i+1}$$$. For example, consider the array $$$[4,6,7,2,2,3]$$$, it will be cut into $$$[4], [6], [7, 2, 2], [3]$$$. All these small subarrays are non-increasing, which means that any subsequence of such a subarray is non-increasing. Because an almost-increasing subsequence cannot have three consecutive elements $$$x \geq y \geq z$$$, in each of the subarrays of our partition at most $$$2$$$ elements can be chosen to insert into our almost-increasing subsequence.
Actually we can put exactly $$$\min( \text{|subarray|}, 2)$$$ elements of each subarray into the increasing subsequence, by taking the first and the last element of each subarray. This is valid, because the cuts for the partition were made at places where $$$a_i < a_{i+1}$$$, so every $$$b_i \geq b_{i+1}$$$ in our candidate subsequence is preceded and followed by a $$$b_j < b_{j+1}$$$. By our upperbound, this construction is optimal.
The sum, $$$ \sum_\limits \text{partition} \min( \text{|subarray|}, 2)$$$ can be calculated for one query in linear time, giving a $$$O(n q)$$$ solution.
To optimize this, the sum $$$ \sum_\limits \text{partition} \min( \text{|subarray|}, 2)$$$ can be rewritten to $$$ \sum_\limits \text{partition}|\text{subarray}| - |\text{inner elements}|$$$, where inner elements of a subarray are all the elements that are not the first or last element. For such elements $$$a_i$$$, we know that $$$a_{i-1} \geq a_i \geq a_{i+1}$$$. The sum of lengths over the partition sums to $$$r-l+1$$$. So we're left with counting the number of special indices $$$l < i < r$$$ such that $$$a_{i-1} \geq a_i \geq a_{i+1}$$$. This can be done with $$$O(n)$$$ preprocessing and $$$O(1)$$$ queries using prefix sums. For a query we can output $$$r-l+1 - |\textit{special} \ \text{indices}|$$$. There are some literal edgecases, where some care in the implementation is needed.
The total time complexity is $$$O(n+q)$$$.