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

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

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