Задача . E. Наибольшие возрастающие подпоследовательности

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

Нам записал последовательность a, состоящую из n (1 ≤ n ≤ 10⁵) элементов a₁, a₂, ..., a_n (1 ≤ a_i ≤ 10⁵). Подпоследовательность a_i1, a_i2, ..., a_ik, где 1 ≤ i₁ < i₂ < ... < i_k ≤ n называется возрастающей, если a_i1 < a_i2 < a_i3 < ... < a_ik. Возрастающая подпоследовательность называется наибольшей, если она обладает максимальной длиной среди всех возрастающих подпоследовательностей.

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

1. группа всех i, таких, что a_i не является элементом ни одной наибольшей возрастающей подпоследовательности.
2. группа всех i, таких, что a_i является элементом по крайней мере одной, но не каждой наибольшей возрастающей подпоследовательности.
3. группа всех i, таких, что a_i является элементом каждой наибольшей возрастающей подпоследовательности.

Так как количество наибольших возрастающей подпоследовательностей a может быть очень большим, произвести подобное разделение очень непросто. Ваша задача — помочь Наму справиться с этим.