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

У Кёрка есть бинарная строка $$$s$$$ (строка, содержащая только нули и единицы) длины $$$n$$$, и он просит вас найти бинарную строку $$$t$$$ такой же длины, для которой выполняются следующие условия:

• Для любых $$$l$$$ и $$$r$$$ ($$$1 \leq l \leq r \leq n$$$) длина наибольшей неубывающей подпоследовательности в подстроке $$$s_{l}s_{l+1} \ldots s_{r}$$$ равна длине наибольшей неубывающей подпоследовательности в подстроке $$$t_{l}t_{l+1} \ldots t_{r}$$$;
• Количество нулей в строке $$$t$$$ — максимально возможное.

Неубывающая подпоследовательность в строке $$$p$$$ — это такая последовательность индексов $$$i_1, i_2, \ldots, i_k$$$, что $$$i_1 < i_2 < \ldots < i_k$$$ и $$$p_{i_1} \leq p_{i_2} \leq \ldots \leq p_{i_k}$$$. Число $$$k$$$ называется длиной подпоследовательности.

Если существует несколько строк, удовлетворяющих условиям, то выведите любую.