비팔로는 원래 사람 말을 절대 듣지 않는 고집불통 동물이다. 하지만 잘만 길들이면 조금씩 말을 듣기 시작한다!

정규는 결심했다. "내가 세상에서 가장 말을 잘 듣는 비팔로를 길들이고야 말겠다!"

비팔로는 \(2\)가지 행동으로 길들임 수치를 올려 길들일 수 있다.

\(1\). 비팔로를 타고 달리기

\(2\). 빗으로 쓸어주기

\(1\)번의 경우 길들임 수치가 \(3\)만큼 증가한다. \(2\)번의 경우 연속해서 빗질한 날 만큼 길들임 수치가 증가하는데, 첫날에는 \(1\)만큼 길들임 수치가 증가하고, 이후 하루씩 추가할 때마다 증가 폭이 \(1\)씩 증가하여 최대 \(5\)까지 길들임 수치를 증가 시킬 수 있다.

매일 비팔로를 타고 달려주기도 하고 빗어주기도 하면 좋겠지만, 하루는 짧기 때문에 하루에 하나의 행동만 수행할 수 있다.

하지만, 비가 오는 날엔 비팔로가 가만히 있질 않기 때문에 빗어줄 수가 없어서, 무조건 타고 달려야 한다.

예를 들어, 아래처럼 길들임 수치를 증가시킬 수 있다.

다행히도 날씨의 아이 정규는 날씨를 예측할 수 있다.

비팔로는 길들임 수치가 증가할 수록 사람의 말을 잘 듣기 때문에, 정규는 \(𝑁\)일 동안 최대한 비팔로의 길들임 수치를 올리고 싶다.

\(𝑁\)일 동안의 날씨가 주어질 때, \(𝑁\)일 동안 정규가 얻을 수 있는 최대 길들임 수치를 구해보자.

입력 설명

입력은 두 줄로 이루어져 있다.

첫째 줄에는 \(𝑁 (1 \le 𝑁 \le 100,000)\)이 주어진다.

둘째 줄에는 \(𝑁\)개의 날씨 \(k\)_\(i\)\((1 \le 𝑁 \le 100,000)\)가 공백으로 구분되어 주어진다.

\(0\): 비가 안 옴 \(1\): 비가 옴

출력 설명

\(𝑁\)일 동안의 최대 길들임 수치를 출력한다.

예제 입력 1

10
0 0 0 0 0 0 0 1 0 0

예제 출력 1

34

예제 입력 2

10
1 1 0 0 0 1 0 0 1 1

예제 출력 2

30

예제 입력 3

8
0 0 0 0 0 0 0 0

예제 출력 3

30

Notes

1번 예제 입출력에서, \(1-7\)일은 비팔로를 빗어주고 \(8-10\)일은 비팔로를 타고 달리면 아래와 같이 길들임 수치를 얻을 수 있다.

\(+1\) \(+2\) \(+3\) \(+4\) \(+5\) \(+5\) \(+5\) \(+3\) \(+3\) \(+3\)

이 경우 최대 길들임 수치 \(34\)를 얻을 수 있다.

달려달려!!