Волонтерство
Волонтерство
Не так добре відомо, що у вільний час пан Малнар робить свій внесок у співтовариство, займаючись волонтерською діяльністю. Це вірно! Він досить активно працює у волонтерському центрі з проблем інформатики.
Нещодавно йому зателефонували з центру і, як виявилося, не вистачає послідовностей, що зростають. Містер Малнар, завжди готовий допомогти, охоче відгукнувся. А саме, він зберігає масив із $n$ цілих чисел саме для цієї мети. Всі цілі числа від $1$ до $n$ зустрічаються в його масиві рівно один раз.
Містер Малнар вибере зі свого масиву кілька зростаючих підпослідовностей, які передасть до центру, а решта збереже для іншого часу. Слід зазначити, що кожне з масиву може використовуватися не більше ніж для однієї послідовності, тобто обрані послідовності мають різні індекси.
Підпослідовність визначається як будь-яка послідовність, отримана з масиву шляхом видалення деяких (можливо, жодного) елементів за збереження порядку інших елементів. Підпослідовність називається зростаючою, якщо кожне число в підпослідовності (крім першого) більше за попереднє.
Оскільки пан Малнар дуже щедрий, він хоче, щоб усі послідовності, які він жертвує, були найдовшими зростаючими підпослідовностями. Іншими словами, якщо $l$ - довжина найдовшої зростаючої підпослідовності вихідного масиву, пан Малнар вибере пару зростаючих підпослідовностей, що не перетинаються, кожна довжиною $l$.
Містер Малнар хоче пожертвувати якнайбільше підпослідовностей. Для заданого масиву містера Малнара виведіть максимальну кількість послідовностей, що становлять його вибір, і наведіть приклад такого вибору.
Вхідні дані
Перший рядок містить ціле число $n$ ($1 ≤ n ≤ 10^6$) - розмір масиву.
Другий рядок містить $n$ чисел $p_i$ ($1 ≤ p_i ≤ n$), що представляють елементи масиву. Кожне позитивне ціле число $j$ між $1$ і $n$ зустрічається в масиві рівно один раз.
Вихідні дані
У першому рядку виведіть максимально можливу кількість підпослідовностей у виборі містера Малнара, а також довжину найдовшої підпослідовності, що зростає.
У кожному з наступних рядків виведіть одну з підпослідовностей такого вибору. Підпослідовність визначається переліком позицій, тобто. індексів масиву, які мають бути відсортовані у порядку зростання.
Підпослідовності, що виводяться, повинні бути зростаючими, непересічними і мати однакову довжину - довжину найдовшої зростаючої підпослідовності.
Відносний порядок підпослідовностей не має значення. Також, якщо рішень кілька, можна вивести будь-яке.
Note
Розглянемо пояснення третього прикладу:
Довжина найдовшої зростаючої підпослідовності дорівнює $3$. Підпослідовність, що визначається індексами $1$, $3$ і $5$ (або значеннями $2$, $6$ і $7$), є зростаючою. Підпослідовність, що визначається індексами $2$, $6$ і $7$ (або значеннями $1$, $3$ і $4$), також є зростаючою. У двох підпослідовностей немає загальних елементів і вони також мають максимальну довжину, тому це допустимий вибір. Неможливо вибрати більше двох таких послідовностей.
3 1 2 3
1 3 1 2 3
4 4 3 2 1
4 1 1 2 3 4
7 2 1 6 5 7 3 4
2 3 1 3 5 2 6 7