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