D-四散而逃_河南萌新联赛2024第（六）场：郑州大学

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

有一个由n个格子排成一行的走廊，边缘的格子为走廊的尽头（即 $1$ 号格子和 $n$ 号格子）, 起初第 $i$ 个格子上都有 $a_i$ 个人。每次**奔逃**操作会使得同一个格子的两个人，向两侧奔逃到某个格子停下。即每次操作会选择三个下标 $i,j,k$ , 其中 $1 \le i<j<k \le n$ ，并且 $a_j \ge 2$ , 从 $j$ 号格子中选择两个人分别逃到 $i$ 号格子和 $k$ 号格子。

问最少需要多少次**奔逃**才能够让所有人都到达 $1$ 号格子或者 $n$ 号格子。若无论多少次操作都做不到，就输出`-1`

*注：应该说是二散而逃才对(o´罒`o)*

输入描述:

第一行输入一个整数

第二行输入n个整数

输出描述:

输出一个整数，表示需要最少的次数，或者-1

示例1

输入

复制

5
1 2 2 3 6

输出

复制

示例2

输入

复制

3
1 3 1

输出

复制

-1