Bazbesonin 国家目前有 $N$ 座城市（编号从 $1$ 到 $N$），它们之间由双向道路连接。当一对城市 $u$ 和 $v$ 想要交换信息时，延迟定义为从 $u$ 到 $v$ 所需的最少道路数量。

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

• 如果城市 $x$ 建成时经济状况良好，则会建造连接城市 $x$ 与之前已建成的所有城市之间的道路。换句话说，对于所有 $1 \le y < x$，都会建造连接城市 $x$ 和城市 $y$ 的道路。
• 如果城市 $x$ 建成时经济状况不佳，则只会建造连接城市 $x$ 和城市 $x-1$ 的道路。

Bazbesonin 的经济状况由二进制数组 $E_{1 \dots N-1}$ 表示。如果城市 $x$ 建成时经济状况良好，则 $E_{x-1}$ 的值为 $1$。否则，$E_{x-1}$ 的值为 $0$。

回到今天，这 $N$ 座城市中的每一座都希望与其他所有城市交换信息。交换的瓶颈定义为所有城市对之间的最大延迟。我们需要计算该信息交换的瓶颈。

例如，设 $N = 5$ 且 $E_{1 \dots 4} = [1, 0, 1, 0]$。Bazbesonin 的城市和道路可以用下图表示：

• 城市 $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 \le N \le 100\,000$)，表示 Bazbesonin 的城市数量。下一行包含 $N-1$ 个整数 $E_i$ ($E_i \in \{0, 1\}$)，表示 Bazbesonin 的经济状况。

输出格式

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

样例

样例输入 1

5
1 0 1 0

样例输出 1

2

说明 1

这是题目描述中的示例。

样例输入 2

7
1 1 1 1 1 1

样例输出 2

1

说明 2

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