说明

巴兹贝索宁国目前有 $N$ 座城市（编号从 $1$ 到 $N$），由双向道路连接。当一对城市 $u$ 和 $v$ 想要交换消息时，延迟 定义为从 $u$ 到 $v$ 所需的最少道路数量。

这些城市有着悠久的历史。最初，城市 $1$ 建在巴兹贝索宁的中部。此后，其余城市从 $2$ 到 $N$ 依次建造。在建造城市 $x$ 时，根据当时的经济状况，会同时修建一条或多条双向道路。

• 如果城市 $x$ 是在经济景气时建造的，则会修建连接城市 $x$ 与所有先前已建城市的道路。也就是说，对于所有 $1 \leq y < x$，修建连接城市 $x$ 和城市 $y$ 的道路。
• 如果城市 $x$ 是在经济不景气时建造的，则只修建连接城市 $x$ 和城市 $x-1$ 的道路。

巴兹贝索宁的经济状况由二进制数组 $E_{1...N-1}$ 表示。如果在建造城市 $x$ 时经济景气，则 $E_{x-1}$ 的值为 $1$，否则为 $0$。

回到现在，$N$ 座城市中的每一座都想与其他所有城市交换消息。交换的瓶颈是所有城市对之间延迟的最大值。我们需要计算消息交换的瓶颈。

例如，令 $N = 5$，$E_{1...4} = [1, 0, 1, 0]$。巴兹贝索宁的城市和道路可由下图说明：

:::align{center} :::

• 城市 $1$ 和城市 $2$ 的延迟为 $1$。
• 城市 $1$ 和城市 $3$ 的延迟为 $2$。
• 城市 $1$ 和城市 $4$ 的延迟为 $1$。
• 城市 $1$ 和城市 $5$ 的延迟为 $2$。
• 城市 $2$ 和城市 $3$ 的延迟为 $1$。
• 城市 $2$ 和城市 $4$ 的延迟为 $1$。
• 城市 $2$ 和城市 $5$ 的延迟为 $2$。
• 城市 $3$ 和城市 $4$ 的延迟为 $1$。
• 城市 $3$ 和城市 $5$ 的延迟为 $2$。
• 城市 $4$ 和城市 $5$ 的延迟为 $1$。

因此，本例中的瓶颈为 $2$。

输入格式

输入第一行包含一个整数 $N$（$2 \leq N \leq 100\,000$），表示巴兹贝索宁的城市数量。下一行包含 $N-1$ 个整数 $E_i$（$E_i \in \{0,1\}$），表示巴兹贝索宁的经济状况。

输出格式

输出一行一个整数，表示消息交换的瓶颈。

5
1 0 1 0

2

7
1 1 1 1 1 1

1

提示

样例 #1 解释

此为题目描述中的示例。

样例 #2 解释

每一对城市之间都由道路直接相连，因此它们的延迟均为 $1$。

翻译由 DeepSeek 完成