给定长度为 $$$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$$$。
回想一下,如果 $$$b$$$ 可以通过删除几个(可能为零或全部)元素来获得,则序列 $$$b$$$ 是序列 $$$a$$$ 的子序列。
然而,他讨厌单调的东西,他想找到一个没有单调三元组的子序列。此外,他希望为每个查询找到一个不包含单调三元组的子序列中长度最大的一个子序列。
请帮助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$$$。
如果有多个最大长度的答案,则打印其中任何一个。
示例
输入 #1
6 2 3 1 4 1 5 9 1 3 4 6
输出 #1
3 1 2 3 0
注意
对于第一个查询,给定的序列本身是无单调三元组的。
对于第二个查询,可以证明不存在长度大于 $$$2$$$ 的子序列 $$$b$$$ 使得 $$$b$$$ 是单调三元组。