题目描述

给定一个字符串 $S$，其中每个字符都是 0、1 或 ?。

构造一个字符串 $S'$，将 $S$ 中的每个 ? 替换为 0 或 1（我们可以独立选择每个 ? 的字符）。我们定义 $S'$ 的不平衡度如下：

• （$S'$ 的不平衡度）\= \\max \\{在 $S$ 的第 $l$ 个和第 $r$ 个字符之间（包括两端）出现的 0 和 1 的次数之差的绝对值：1 \\leq l \\leq r \\leq |S|\\}

找到 $S'$ 的最小可能不平衡度。

约束条件

• $1 \\leq |S| \\leq 10^6$
• $S$ 的每个字符都是 0、1 或 ?。

输入

输入以标准输入格式给出，格式如下所示：

$S$

输出

打印 $S'$ 的最小可能不平衡度。

示例输入 1

0??

示例输出 1

1

我们可以构造 $S'=$ 010，并达到最小可能的不平衡度 $1$。

示例输入 2

0??0

示例输出 2

2

示例输入 3

??00????0??0????0?0??00??1???11?1?1???1?11?111???1

示例输出 3

4