눈 쌓인 길

라트비아에는 이번 겨울 눈이 유난히 자주 내린다. 어제 저녁 Mārtiņš는 집으로 이어지는 길을 깨끗이 치웠다. 그런데 오늘 아침 잠에서 깨어 창밖을 보니 길이 다시 눈에 덮여 있었다. 오늘 Mārtiņš가 길의 눈을 치우는 데 쓰는 에너지의 양을 구하라.

길은 길이가 $N$ 미터인 직선 구간이다. 길을 덮은 눈은 고르지 않다. 첫 번째 미터에는 깊이 $a_1$ 센티미터의 눈이, 두 번째 미터에는 $a_2$ 센티미터의 눈이 쌓여 있고, 이런 식으로 마지막 $N$ 번째 미터에는 $a_N$ 센티미터의 눈이 쌓여 있다.

Mārtiņš는 첫 번째 미터부터 길을 치우기 시작한다. 그 자리의 눈을 삽으로 모두 떠서 자기 몸에서 위쪽, 멀리 던진다. 던진 눈은 다시 길에 떨어져 가까운 몇 미터를 1 센티미터 두께로 덮는다. 다음 그림을 보자.

그림 1. 3 센티미터 두께의 눈이 3미터 구간에 퍼진다.

첫 번째 미터를 치운 뒤 Mārtiņš는 두 번째 미터로 넘어간다. 그곳의 눈을 위로 던지면 눈은 다시 가까운 몇 미터를 1 센티미터 두께로 덮는다. 이어서 세 번째, 네 번째 미터를 같은 방식으로 치우며, 길에 눈이 남지 않을 때까지 계속한다. 예시는 이렇게 이어진다.

그림 2. 길을 치우는 과정. 길 밖으로 떨어진 눈은 그곳에 그대로 남는다.

Mārtiņš는 $a$ 센티미터의 눈을 위로 던질 때마다 $a$ 에너지 단위를 쓴다. 위 예시에서 그가 쓰는 에너지는 모두 합쳐 $3 + 2 + 4 + 3 + 3 = 15$ 단위이다.

첫째 줄에 길의 길이 $N$이 정수로 주어진다.

둘째 줄에는 길을 덮은 눈의 깊이를 나타내는 정수 $a_1, a_2, \dots, a_N$이 공백으로 구분되어 주어진다.

Mārtiņš가 쓰는 에너지의 양을 한 줄에 출력한다.

• $1 \le N \le 1\,000\,000$
• $0 \le a_i \le 1\,000\,000\,000$