日本积极开展防灾研究,近年来其重要性不断增加。 疏散路线的评估也是一个重要的研究领域。 这次我们来评估一下直道的安全性。
该段落是 从一端的单元到另一端的单元,分为 W 个单元。 它的编号为 1, 2, 3, … , W 。 通道中的每个单元都有以下门之一:入口门、出口门或防火门。 一条通道内可以有多个入口门、出口门和防火门。
在这个问题中,时间 假设 t=0 发生火灾。 因此,在通道外试图疏散的人们会从入口门进入通道,并试图从出口门逃生到更安全的地方。 每个被疏散的人每单位时间可以移动一个单位或留在当前单位。 换句话说,时间 t 中的一个人是一个单位 当一个人处于 i 时,时间 t+1 单位 三个数字中的 i-1, i, i+1 三个数字中 1 以上 W 您可以选择以下内容并移动到具有该编号的单位。 设有防火门的单位在一定时间后会完全关闭,使疏散人员无法进入单位。此外,该单位的人员将无法从该单位转移到其他单位。
该问题的目的是根据每扇门的信息,计算在疏散人员表现最佳的情况下能够到达出口门的最大人数。
通道信息 它由W整数a_i给出。 当
- a_i = 0时, 表示第i 个单元是出口门。
- a_i < 0时, 表示第i 该装置由防火门启动。 |a_i| 表示您将无法再进入或退出。
- a_i > 0时, 表示第i 表示单位为入户门,时间 每个 t=0, 1, 2, … , a_i-1 中只有一个人 出现在第 i 个单位中。时间 出现在 t 的人是 从 t+1 开始移动。
找出能够到达出口的最大人数。
入力形式
输入按以下格式给出
W a_1 a_2 ... a_W
出力形式
输出一行中的最大人数。
制約
- 1 ≤ W ≤ 10^5
- |a_i| ≤ 10^4
- 所有输入值都是整数。 第
入出力例
入力例 1
7 2 0 -2 3 2 -2 0
出力例 1
4
1, 4, 5个单元有一个入口门,
第
2, 6单元有一个出口门。
从第
1单元开始,2单位中可以出现两个人。
一个人可以前往第
4单元开始,2个单位。
5单元开始,7个单位。
因此,总共有四个人可以到达出口。
入力例 2
4 1 1 1 1
出力例 2
0
没有人可以逃脱,因为没有出口。
入力例 3
9 10 -10 10 -10 10 -10 10 -10 0
出力例 3
24