您有一个有向无环图 G,由 n 个顶点组成,编号从 0 到 n - 1。该图包含 n 条边,编号从 0 到 n - 1。编号为 i 的边连接顶点 i 和 (i + 1) mod n,并且它可以指向任一方向(从 i 到 (i + 1) mod n,反之亦然)。
运算 x mod y 表示取数字 x 除以数字 y 后的余数。
如果图包含从 u 到 v 或从 v 到 u 的路径,我们称图 G 中的两个顶点 u 和 v 为可比较的。我们假设反链是图 G 的一组顶点,其中任何两个不同的顶点都不具有可比性。反链的大小是相应集合中顶点的数量。如果图没有更大尺寸的反链,则反链是最大的。
你的任务是找到图 G 中最大反链的大小。
输入
第一行包含字符序列 s0s1... sn - 1 (2 ≤ n ≤ 106),由数字 0 和 1 组成。线的长度(编号 n)对应于图 G 中的顶点和边的数量。如果字符 si (i ≥ 0) 等于 0,则顶点 i 和 (i + 1) mod n 之间的边从第 i 个顶点指向第 (i + 1) mod n 个顶点,否则指向相反的点。
保证给定的图是非循环的。
输出
打印单个整数 — 图 G 的最大反链的大小。
示例
输入 #1
001
输出 #1
1
输入 #2
110010
输出 #2
3
注意
考虑第一个测试样本。图的G边为:0→1、1→2、0→2。我们可以选择顶点集合[0]作为最大反链。我们不能选择更大尺寸的反链。