题目描述

为了逃离地球，小黄正在锻炼虚空行走的能力。

现在小黄将每隔 $1$ 天文单位设立一个空间坐标，合计标记了 $n$ 个坐标，其中 $1$ 号坐标是起点，也就是地球，$n$ 号坐标是旅行的终点，小黄将只经过这些坐标而到达终点。假设小黄现在的空间行走等级为 $x$，那么小黄就可以在一次虚空行走时最多跳跃 $x$ 天文单位的距离，也就是说，如果小黄当前在 $i$ 号坐标，那么一次虚空行走可以跳跃到 $[i + 1, i + x]$ 中的任意一个坐标。

但小黄很快了解到，由于大能任意行走虚空，导致虚空破碎，很多被小黄标记好的坐标是不稳定的，如果跳跃到不稳定的坐标处小黄将会遭遇不可预测的危险！但小黄不打算修改自己的旅途，他已经通过情报得知这些坐标中哪些是不稳定而危险的，小黄想要知道，他至少需要将虚空行走锻炼到哪个等级，就可以保证安全的到达终点。

保证起点和终点是安全稳定的。

输入输出格式

输入格式

第一行包含一个正整数 $n$，表示坐标的数量。

第二行包含 $n$ 个整数 $a_i$，表示编号为 $i$ 的坐标处是否稳定。如果 $a_i = 1$ 则该坐标处是安全稳定的，如果 $a_i = 0$ 则该坐标处是不稳定的。

输出格式

输出一个整数，表示小黄至少需要的虚空行走等级。

样例

5
1 0 1 0 1

2

5
1 1 0 0 1

3

数据范围

对于 $20\%$ 的数据，满足 $1 \leq n \leq 50$，除起点终点外所有 $a_i$ 均为 $0$

对于 $40\%$ 的数据，满足 $1 \leq n \leq 1000$，除起点终点外有且仅有一个 $a_i=1$

对于 $100\%$ 的数据，满足 $1 \leq n \leq 1000$

对于所有数据保证起点和终点的 $a_i=1$