Background

Translated from ROI 2019 D2T1。

For a sequence consisting of 0 and 1, the definition of “beautiful” is: if the number of 0 before the first 1 equals the number of 0 after the last 1, and the number of 0 between every two adjacent 1 is also equal to this value, then the sequence is called “beautiful”。

For example, 0101010 and 11111 are “beautiful”, but 10101 and 010100001000001010000 are not “beautiful”。

Problem Description

Given a sequence consisting of 0 and 1 (it is guaranteed that the number of 1 is not $0$), you need to delete some elements at arbitrary positions so that the remaining sequence forms the longest possible beautiful string.

Input Format

The first line contains an integer $n$, the length of the sequence。

The second line contains a string $s$, consisting only of 0 and 1, representing the sequence。

Output Format

The first line outputs an integer $m$, the length of the remaining sequence after deletions。

The second line outputs the “beautiful” sequence that remains after the deletions。

If there are multiple solutions, output any one。Note: a string consisting entirely of 0 is not “beautiful”。

10
0100100000

7
0001000

3
111

3
111

7
0100101

5
01010

Hint

Suppose the original string has $k$ 1s。

Translated by ChatGPT 5