题目描述

译自 ROI 2019 Day2 T1. Гирлянда

对于一个 01 串，如果它可以被表示为 A1A1A……1A 的形式，其中

• A 是若干个 0 或空串，且
• 每个 A 包含的 0 数量相等，且
• 首尾都是 A，中间有至少一个 1

则称这是一个「美丽的」01 串。

给一个 01 串，请删除尽量少的数字，使得剩下的数字形成一个美丽的 01 串。

Гирлянда — это цепочка из элементов: флажков и шариков, содержащая хотя бы один флажок. Длиной гирлянды называется количество элементов, из которых она состоит.

Гирлянда считается красивой, если для каждого флажка количество подряд идущих шариков слева от него до ближайшего слева флажка или до начала гирлянды равно количеству подряд идущих шариков справа от него до ближайшего справа флажка или до конца гирлянды.

Обозначим шарик символом «0», а флажок — символом «1». Например, гирлянда «0001000» является красивой, а гирлянда «001010» — нет, поскольку слева от первого флажка два шарика, а справа от него — один шарик. Отметим, что цепочка «000» не является гирляндой, так как не содержит ни одного флажка.

Задана гирлянда, разрешается удалить некоторые её элементы.

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

10
0100100000

7
0001000

3
111

3
111

7
0100101

5
01010

数据范围与提示

对于所有数据，$1 ⩽ n ⩽ 500000$。

设 $k$ 表示输入的 01 串中 1 的个数。