연속 가동 보상 기록

문제

한 게임 서버는 정해진 점검 구간마다 훈련장 이용 횟수를 기록한다. 운영자는 훈련장이 꾸준히 사용되는지 확인하기 위해 각 구간에 보상 점수를 부여하고, 모든 구간의 점수를 합산한다. 점검 구간은 1번부터 N번까지 시간순으로 이어져 있으며, 각 구간의 이용 횟수는 음이 아닌 정수다. 이용 횟수가 1 이상인 구간을 가동 구간이라고 한다. 가동 구간의 기본 점수는 해당 구간의 이용 횟수와 같다. 여기에 현재 구간까지 가동 구간이 연속으로 이어진 길이를 추가 점수로 더한다. 연속 길이는 현재 구간을 포함하여 세며, 기록의 첫 구간 이전에는 가동 구간이 없었다고 생각한다. 예를 들어 이용 횟수가 차례로 2, 5, 1이라면 세 구간의 연속 길이는 각각 1, 2, 3이다. 따라서 각 구간의 점수는 각각 3, 7, 4가 된다. 이용 횟수의 크기가 앞 구간보다 작아져도 1 이상이기만 하면 연속 길이는 계속 증가한다. 추가 점수는 이용 횟수에 곱하는 값이 아니라 기본 점수에 한 번 더하는 값이다. 이용 횟수가 0인 구간의 점수는 0이다. 이 구간에서는 연속 길이도 0으로 초기화한다. 이후 다시 가동 구간이 나오면 연속 길이를 1부터 새로 센다. 이용 횟수가 0인 구간이 여러 번 이어져도 별도의 감점은 없으며, 이미 얻은 점수가 사라지지도 않는다. 각 구간의 점수는 그 구간까지의 기록만으로 결정된다. 뒤에 이용 횟수가 0인 구간이 나타나더라도 앞 구간의 추가 점수를 바꾸지 않는다. 전체 기록에 가동 구간이 하나도 없다면 합계는 0이다. 주어진 기록을 시간순으로 처리하여 N개 구간에서 얻은 점수의 합을 구하는 프로그램을 작성한다.

입력

첫째 줄에 점검 구간의 수 N이 주어진다.
둘째 줄에 각 구간의 이용 횟수 X_1, X_2, …, X_N이 공백으로 구분되어 주어진다.
모든 입력값은 정수다.
1 ≤ N ≤ 1,000
0 ≤ X_i ≤ 1,000

출력

첫째 줄에 모든 점검 구간의 점수 합을 정수로 출력한다. 가동 구간이 없으면 0을 출력한다.

6
2 5 0 1 1 3

21

4
0 0 0 0

0

3
1 1 1

9

출처: Devin.KR 자체 제작