Волонтерство

Не так хорошо известно, что в свободное время г-н Малнар вносит свой вклад в сообщество, занимаясь волонтерской деятельностью. Это верно! Он довольно активно работает в волонтерском центре по проблемам информатики.

Недавно ему позвонили из центра и, как оказалось, не хватает возрастающих последовательностей. Мистер Малнар, всегда готовый помочь, с готовностью откликнулся. А именно, он хранит массив из $n$ целых чисел именно для этой цели. Все целые числа от $1$ до $n$ встречаются в его массиве ровно один раз.

Мистер Малнар выберет из своего массива несколько возрастающих подпоследовательностей, которые передаст в центр, а остальные числа сохранит для другого времени. Следует отметить, что каждое число из массива может использоваться не более чем для одной подпоследовательности, то есть выбранные подпоследовательности имеют разные индексы.

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

Поскольку г-н Малнар очень щедр, он хочет, чтобы все последовательности, которые он жертвует, были самыми длинными возрастающими подпоследовательностями. Другими словами, если $l$ - длина самой длинной возрастающей подпоследовательности исходного массива, г-н Малнар выберет пару непересекающихся возрастающих подпоследовательностей, каждая длиной $l$.

Мистер Малнар хочет пожертвовать как можно больше подпоследовательностей. Для заданного массива мистера Малнара выведите максимальное количество подпоследовательностей, составляющих его выбор, и приведите пример такого выбора.

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

Первая строка содержит целое число $n$ ($1\le n\le 10^6$) - размер массива.

Вторая строка содержит $n$ чисел $p_i$ ($1\le p_i\le n$), представляющих элементы массива. Каждое положительное целое число $j$ между $1$ и $n$ встречается в массиве ровно один раз.

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

В первой строке выведите максимально возможное количество подпоследовательностей в выборе мистера Малнара, а также длину самой длинной возрастающей подпоследовательности.

В каждой из следующих строк выведите одну из подпоследовательностей из такого выбора. Подпоследовательность определяется списком позиций, т.е. индексов массива, которые должны быть отсортированы в порядке возрастания.

Выводимые подпоследовательности должны быть возрастающими, непересекающимися и иметь одинаковую длину - длину самой длинной возрастающей подпоследовательности.

Относительный порядок подпоследовательностей не имеет значения. Также, если решений несколько, можно вывести любое.

Примеры

Примечание

Рассмотрим пояснение третьего примера:

Длина самой длинной возрастающей подпоследовательности равна $3$. Подпоследовательность, определяемая индексами $1$, $3$ и $5$ (или значениями $2$, $6$ и $7$), является возрастающей. Подпоследовательность, определяемая индексами $2$, $6$ и $7$ (или значениями $1$, $3$ и $4$), также является возрастающей. У двух подпоследовательностей нет общих элементов, и они также имеют максимальную длину, поэтому это допустимый выбор. Невозможно выбрать более двух таких подпоследовательностей.