CF1332G.No Monotone Triples

Given a sequence of integers $a$ of length $n$, a tuple $(i,j,k)$ is called monotone triples if

• $1 \le i \lt j \lt k\le n$;
• $a_i \le a_j \le a_k$ or $a_i \ge a_j \ge a_k$ is satisfied.

For example, $a=[5,3,4,5]$, then $(2,3,4)$ is monotone triples for sequence $a$ while $(1,3,4)$ is not.

Bob is given a sequence of integers $a$ of length $n$ in a math exam. The exams itself contains questions of form $L, R$, for each of them he is asked to find any subsequence $b$ with size greater than $2$ (i.e. $|b| \ge 3$) of sequence $a_L, a_{L+1},\ldots, a_{R}$.

Recall that an sequence $b$ is a subsequence of sequence $a$ if $b$ can be obtained by deletion of several (possibly zero, or all) elements.

However, he hates monotone stuff, and he wants to find a subsequence free from monotone triples. Besides, he wants to find one subsequence with the largest length among all subsequences free from monotone triples for every query.

Please help Bob find out subsequences meeting the above constraints.

给定一个长度为 $n$ 的整数序列 $a$，若三元组 $(i,j,k)$ 满足以下条件，则称其为单调三元组（monotone triples）：

• $1 \le i \lt j \lt k\le n$；
• 满足 $a_i \le a_j \le a_k$ 或 $a_i \ge a_j \ge a_k$。

例如，当 $a=[5,3,4,5]$ 时，$(2,3,4)$ 是序列 $a$ 的一个单调三元组，而 $(1,3,4)$ 则不是。

鲍勃在一次数学考试中被给定了一个长度为 $n$ 的整数序列 $a$。考试题目包含若干形如 $L, R$ 的询问，对每个询问，他需要在子数组 $a_L, a_{L+1},\ldots, a_{R}$ 中找出一个长度大于 $2$（即 $|b| \ge 3$）的子序列 $b$。

回顾定义：若序列 $b$ 可通过从序列 $a$ 中删除若干（可能为零个、也可能为全部）元素得到，则称 $b$ 是 $a$ 的一个子序列。

然而，鲍勃讨厌一切单调性质，因此他希望找到一个不含任何单调三元组的子序列。此外，对于每个询问，他希望找到所有不含单调三元组的子序列中长度最大者。

请帮助鲍勃找出满足上述所有约束条件的子序列。

The first line contains two integers $n$, $q$ ($3 \le n \le 2 \cdot 10^5$, $1 \le q \le 2 \cdot 10^5$) — the length of sequence $a$ and the number of queries.

The second line contains $n$ integers $a_1,a_2,\ldots, a_n$ ($1 \le a_i \le 10^{9}$), representing the sequence $a$.

Then each of the following $q$ lines contains two integers $L$, $R$ ($1 \le L,R \le n$, $R-L\ge 2$).

第一行包含两个整数 $n$、$q$（$3 \le n \le 2 \cdot 10^5$，$1 \le q \le 2 \cdot 10^5$）—— 分别表示序列 $a$ 的长度和查询次数。

第二行包含 $n$ 个整数 $a_1,a_2,\ldots, a_n$（$1 \le a_i \le 10^{9}$），表示序列 $a$。

接下来的 $q$ 行中，每行包含两个整数 $L$、$R$（$1 \le L,R \le n$，且 $R-L\ge 2$）。

For each query, output $0$ if there is no subsequence $b$ satisfying the constraints mentioned in the legend. You can print the empty line after but that's not mandatory.

Otherwise, output one integer $k$ ($k \gt 2$) denoting the length of sequence $b$, then output $k$ integers $i_1, i_2, \ldots, i_k$ ($L \le i_1 \lt i_2 \lt \ldots \lt i_k\le R$) satisfying that $b_j = a_{i_j}$ for $1 \le j \le k$.

If there are multiple answers with the maximum length, print any of them.

对于每个查询，若不存在满足题面中所述约束条件的子序列 $b$，则输出 $0$。可在其后输出空行，但非必需。

否则，先输出一个整数 $k$（$k \gt 2$），表示序列 $b$ 的长度；然后输出 $k$ 个整数 $i_1, i_2, \ldots, i_k$（满足 $L \le i_1 \lt i_2 \lt \ldots \lt i_k\le R$），使得对所有 $1 \le j \le k$ 均有 $b_j = a_{i_j}$。

若存在多个具有最大长度的答案，输出任意一个即可。

For the first query, the given sequence itself is monotone triples free.

For the second query, it can be shown that there is no subsequence $b$ with length greater than $2$ such that $b$ is monotone triples free.

对于第一个查询，给定序列本身不包含单调三元组。

对于第二个查询，可以证明：不存在长度大于 $2$ 的子序列 $b$，使得 $b$ 不包含单调三元组。