墓碑上的路

题目描述

杨冬的墓碑上有 $n$ 个数字，每个数字都被格式化了。

数字的样子：

***** ..*.. ***** ***** *...*
*...* .**.. ....* ....* *...*
*...* *.*.. ***** ***** *****
*...* ..*.. *.... ....* ....*
***** ***** ***** ***** ....*

***** ***** ***** ***** *****
*.... *.... ....* *...* *...*
***** ***** ....* ***** *****
....* *...* ....* *...* ....*
***** ***** ....* ***** *****

（ * 是可走的，. 是不可走的）

杨冬的墓碑上的数字第一个数字（最后一个不保证）肯定不是 $1$，褐蚁现在在数字 $0$ 的左上角，他要爬到最后一个数字的右下角，墓碑上的数字是相连的（比如从数字 $5$ 的右下角可以爬到数字 $6$ 的左下角），褐蚁想提前知道，它从这一串数字的左上角爬到这一串数字的右下角至少需要走多少步，如果无法走到，输出 $-1$。

注意：褐蚁可以往 $8$ 个方向走（东、西、南、北、东北、东南、西南、西北）。

输入格式

第 $1$ 行，一个正整数 $n$。

第 $2$ 行，表示给出的 $n$ 个整数 $a_i$。

输出格式

一个正整数，为所求的答案。

样例 #1

样例输入 #1

5
0 0 0 0 0

样例输出 #1

25

样例 #2

样例输入 #2

10
0 1 2 3 4 5 6 7 8 9

样例输出 #2

50

提示

对于 $50\%$ 的数据，$n \le 10$。

对于 $100\%$ 的数据，$n \le 30$，$0 \le a_i \le 9$, $a_1 \ne 1$。