CF1332G No Monotone Triples

给定一个长度为 $n$ 的整数序列 $a$，如果三元组 $(i, j, k)$ 满足以下条件，则称其为单调三元组： - $1 \le i < j < 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)$ 不是。 Bob 在一次数学考试中得到了一个长度为 $n$ 的整数序列 $a$。考试中包含若干个形如 $L, R$ 的问题，对于每个问题，他需要在序列 $a_L, a_{L+1}, \ldots, a_R$ 中找到一个长度大于 $2$（即 $|b| \ge 3$）的子序列 $b$。 回忆一下，如果通过删除若干（可能为零或全部）元素可以从序列 $a$ 得到序列 $b$，则称 $b$ 是 $a$ 的一个子序列。 然而，Bob 讨厌单调的东西，他希望找到一个不包含任何单调三元组的子序列。此外，对于每个询问，他希望找到所有不包含单调三元组的子序列中长度最大的一个。 请你帮助 Bob 找出满足上述条件的子序列。

第一行包含两个整数 $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$）。

对于每个询问，如果不存在满足条件的子序列 $b$，输出 $0$。你可以输出一个空行，但不是必须的。 否则，输出一个整数 $k$（$k > 2$），表示子序列 $b$ 的长度，然后输出 $k$ 个整数 $i_1, i_2, \ldots, i_k$（$L \le i_1 < i_2 < \ldots < i_k \le R$），满足 $b_j = a_{i_j}$，其中 $1 \le j \le k$。 如果存在多个长度最大的答案，输出任意一个均可。

对于第一个询问，给定的整个序列本身就不包含单调三元组。 对于第二个询问，可以证明不存在长度大于 $2$ 的、且不包含单调三元组的子序列 $b$。 由 ChatGPT 4.1 翻译