22436번 - Evacuation Route 다국어

日本では防災研究が盛んに行われており，近年その重要性がますます増している． 避難経路の評価も重要な研究のひとつである． 今回は直線状の通路の安全評価を行う．

通路は $W$ 個のユニットに分けられており，一方の端のユニットからもう一方の端のユニットまで $1,  2,  3,  … ,  W$ の番号がつけられている． 通路内の各ユニットには，入口の扉，出口の扉，防火扉のいずれか1つが存在する． 入口の扉，出口の扉，防火扉はそれぞれ通路内に複数個存在しうる．

この問題では時刻 $t=0$ で火災が発生したと想定する． それにより，通路の外部にいて避難しようとしている人々が入口の扉を通じて通路へ入り，より安全な場所へ出るために出口の扉へ脱出しようとするものとする． 避難中のそれぞれの人は単位時刻ごとに 1 つのユニットを移動するか，今のユニットに留まることができる． すなわち，時刻 $t$ にある人がユニット $i$ にいたとするとき，その人は時刻 $t+1$ ではユニット $i-1,  i,   i+1$ の3つの数字のうち $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$ 以降から移動を開始する．

なお，1つのユニットに複数の人々が存在してもかまわない．

出口の扉へたどり着ける最大の人数を求めよ．

入力は以下の形式で与えられる

$W$

$a_1$ $a_2$ $...$ $a_W$

最大人数を1行で出力せよ．

• $1 ≤ W ≤ 10^5$
• $|a_i|   ≤ 10^4$
• 入力値はすべて整数である．