题目描述

艾扎克有一个长度为 $N$ 的数组 $A$ ，$A_i$ 表示在位置 $i$ 处有一个空地（$A_i = 0$）或一只生命值为 $A_i$ 的怪物（$A_i \gt 0$）.

艾扎克有一个弹球，可以在任意空地上放置，并向左或者向右发射，每当弹球碰到怪物时，怪物的生命值会减小 $1$ 个单位，并且弹球的运动方向变为原来的反方向. 当怪物的生命值减为 $0$ 时，怪物会消失.

艾扎克想知道他有多少种方案能够打败所有怪物. 两种方案不同当且仅当这两种方案放置球的起始空地位置或者球的发射方向不同.

输入格式

第 $1$ 行，一个数字 $N$，表示数组长度.

第 $2$ 行，有 $N$ 个数，表示 $A_1, A_2,...,A_N$ .

输出格式

输出有多少种方案.

样例输入

4
4 0 1 3

样例输出

2

数据范围

对于 $40\%$ 的数据，满足 $3\le N \le 10^3$, $0 \le A_i \le 10^9$

对于 $100\%$​ 的数据，满足 $3\le N \le 10^5$, $0 \le A_i \le 10^9$