대피 경로

일본에서는 방재 연구가 활발히 이루어지고 있으며, 최근 그 중요성이 더욱 커지고 있다. 대피 경로의 평가도 중요한 연구 주제 중 하나이다. 이번에는 직선 형태의 통로에 대한 안전성을 평가한다.

통로는 $W$개의 유닛으로 나뉘어 있고, 한쪽 끝 유닛부터 다른 쪽 끝 유닛까지 $1, 2, 3, \ldots, 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, \ldots, a_i-1$ 각각에서 정확히 한 사람이 $i$번째 유닛에 나타난다. 시각 $t$에 나타난 사람은 시각 $t+1$부터 이동을 시작한다.

한 유닛에 여러 사람이 있어도 된다.

출구 문에 도달할 수 있는 최대 사람 수를 구하여라.

입력은 다음 형식으로 주어진다.

$W$

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

최대 사람 수를 한 줄에 출력하여라.

• $1 ≤ W ≤ 10^5$
• $|a_i| ≤ 10^4$
• 입력값은 모두 정수이다.