D. Колеблющаяся подпоследовательность
ограничение по времени на тест
0.75 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Студент Вася готовится к сдаче лабораторной по физике и решил немного приукрасить данные, полученные в результате эксперимента. В ходе работы Вася измерял некоторую величину и записывал результаты в виде последовательности целых чисел $$$ A = (a_0, a_1, a_2, ..., a_{n - 1}) $$$. Вася хочет оставить в последовательности только те измерения, которые образуют колеблющуюся подпоследовательность $$$ B = (b_0, b_1, b_2, ..., b_{k - 1}) $$$. Последовательность считается колеблющейся, если любой её элемент (кроме крайних) либо строго больше обоих своих соседей $$$(b_{i-1} \gt b_i \lt b_{i+1})$$$, либо строго меньше их $$$(b_{i-1} \lt b_i \gt b_{i+1})$$$. Помогите Васе – напишите программу, которая для последовательности $$$ A = (a_0, a_1, a_2, ..., a_{n - 1}) $$$ найдет ее самую длинную колеблющуюся подпоследовательность $$$ B $$$ длиной не менее трёх.

Входные данные

Первая строка входных данных содержит единственное целое число $$$ n $$$ $$$(1 \leq n \leq 50\,000)$$$ – количество элементов в последовательности $$$ A $$$. Вторая строка содержит $$$ n $$$ целых чисел, разделенных пробелами – элементы последовательности $$$ a_i $$$ $$$(0 \leq i \lt n~,~-10^9 \leq a_i \leq 10^9)$$$.

Выходные данные

Первая строка содержит целое число $$$ k $$$ $$$(3 \leq k \leq n)$$$ – количество оставленных элементов последовательности $$$ A $$$. Вторая строка содержит $$$ k $$$ целых чисел $$$ r_0, r_1, ..., r_{k-1} $$$ $$$(0 \leq r_i \lt n $$$; $$$r_i \lt r_{i+1})$$$, упорядоченных по возрастанию и разделенных пробелами – индексы элементов последовательности $$$ A $$$, формирующих колеблющуюся подпоследовательность. Если такой подпоследовательности не существует – первая строка должна содержать 0.

Если задача имеет несколько решение, выведите любое из них.

Примеры
Входные данные
3
1 3 2
Выходные данные
3
0 1 2
Входные данные
3
1 2 3
Выходные данные
0
Примечание

Подпоследовательность $$$ B $$$ может быть получена из последовательности $$$ A $$$ путем удаления некоторого количества элементов (возможно, нулевого). Порядок элементов при этом сохраняется.

В ответе задачи приводится не сама подпоследовательность $$$ B $$$, а индексы тех элементов $$$ A $$$, которые не были удалены.