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

Не так добре відомо, що у вільний час пан Малнар робить свій внесок у співтовариство, займаючись волонтерською діяльністю. Це вірно! Він досить активно працює у волонтерському центрі з проблем інформатики.

Нещодавно йому зателефонували з центру і, як виявилося, не вистачає послідовностей, що зростають. Містер Малнар, завжди готовий допомогти, охоче відгукнувся. А саме, він зберігає масив із $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$), також є зростаючою. У двох підпослідовностей немає загальних елементів і вони також мають максимальну довжину, тому це допустимий вибір. Неможливо вибрати більше двох таких послідовностей.