No Monotone Triples

题意翻译

定义一个三元组 $(i,j,k)$ 为单调三元组，当且仅当满足 + $i<j<k$ + $a_i\le a_j \le a_k$ 或 $a_i\ge a_j \ge a_k$ 现有一个长度为 $n$ 的序列 $a$ ，和 $q$ 次询问，每次询问给定 $L,R$ ，找到一个最长的**子序列** $b$ ，满足 $|b|\ge 3$ ，且 $b$ 中不含有单调三元组。 对于每个询问，输出 $b$ 中的每个元素在 $a$ 中的**位置**。 $3 \le n \le 2 \cdot 10^5 ,1 \le q \le 2 \cdot 10^5,R-L \ge 2$

题目描述

Given a sequence of integers $ a $ of length $ n $ , a tuple $ (i,j,k) $ is called monotone triples if - $ 1 \le i<j<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.

输入输出格式

输入格式

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

输出格式

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 > 2 $ ) denoting the length of sequence $ b $ , then output $ k $ integers $ i_1, i_2, \ldots, i_k $ ( $ L \le i_1 < i_2<\ldots<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.

输入输出样例

输入样例 #1

6 2
3 1 4 1 5 9
1 3
4 6

输出样例 #1

3
1 2 3 
0

说明

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.