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