Единственное отличие между легкой и сложной версиями — длины строк. Вы можете взламывать эту задачу тогда, когда решите ее. Но предыдущую только тогда, когда решите обе задачи.
У Кёрка есть бинарная строка \(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\) называется длиной подпоследовательности.
Если существует несколько строк, удовлетворяющих условиям, то выведите любую.
Выходные данные
Выведите бинарную строку, для которой выполняются указанные условия. Если существует несколько таких строк, выведите любую.