Вероятно, вам знакома классическая задача нахождения наибольшей возрастающей подпоследовательности в массиве. Пусть \(a\) — массив, состоящий из \(n\) целых чисел. Назовем подпоследовательность \(i_1 < i_2 < \ldots < i_k\) возрастающей , если \(a_{i_1} < a_{i_2} < \ldots < a_{i_k}\). Наибольшей возрастающей подпоследовательностью называется возрастающая подпоследовательность максимальной длины. Конечно, мы не будем предлагать вам решить классическую задачу, вам предстоит решить ее усложненную версию...

Изначально есть пустой массив \(a\). Далее в массив последовательно добавляются числа \(1, 2, \ldots, n\) в этом порядке. При этом число \(i\) добавляется в массив на позицию \(p_i\). Позиции в массиве нумеруются целыми числами от \(1\) до \(k\), где \(k\) — текущий размер массива. При добавлении элемента на позицию \(p\) в массив размера \(k\) все элементы, которые раньше имели позиции от \(p\) до \(k\), сдвигаются на одну позицию вправо, а на освободившееся место добавляется текущий элемент.

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