D. An oscillating subsequence
time limit per test
0.75 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Student Vasya is preparing to submit a physics lab report and decided to slightly embellish the data obtained as a result of the experiment. During the work, Vasya measured a certain value and recorded the results as a sequence of integers $$$ A = (a_0, a_1, a_2, ..., a_{n - 1}) $$$. Vasya wants to leave in the sequence only those measurements that form an oscillating subsequence $$$ B = (b_0, b_1, b_2, ..., b_{k - 1}) $$$. A sequence is considered oscillating if every element (except the first and the last) is either strictly greater than both of its neighbors $$$(b_{i-1} \gt b_i \lt b_{i+1})$$$ or strictly smaller than them $$$(b_{i-1} \lt b_i \gt b_{i+1})$$$. Help Vasya – write a program that, for a sequence $$$ A = (a_0, a_1, a_2, ..., a_{n - 1}) $$$, finds its longest oscillating subsequence $$$ B $$$ with a length of at least three.

Input

The first line of input data contains a single integer $$$ n $$$ $$$(1 \leq n \leq 50\,000)$$$ – the number of elements in the sequence $$$ A $$$. The second line contains $$$ n $$$ integers separated by spaces – the elements of the sequence $$$ a_i $$$ $$$(0 \leq i \lt n~,~-10^9 \leq a_i \leq 10^9)$$$.

Output

The first line contains an integer $$$ k $$$ $$$(3 \leq k \leq n)$$$ – the number of remaining elements of the sequence $$$ A $$$. The second line contains $$$ k $$$ integers $$$ r_0, r_1, ..., r_{k-1} $$$ $$$(0 \leq r_i \lt n $$$; $$$r_i \lt r_{i+1})$$$, ordered in ascending order and separated by spaces – the indexes of the elements of the sequence $$$ A $$$, forming an oscillating a subsequence. If such a subsequence does not exist, the first line must contain 0.

If there are multiple solutions, print any of them.

Examples
Input
3
1 3 2
Output
3
0 1 2
Input
3
1 2 3
Output
0
Note

The subsequence $$$ B $$$ can be obtained from the sequence $$$ A $$$ by removing a certain number of elements (possibly none). The order of the elements is preserved.

The solution should not output the subsequence $$$ B $$$ itself, but rather the indexes of those $$$ A $$$ elements that have not been removed.