Taktsveðjur

Atli는 민망할 정도로 자주 생산적인 일을 하는 대신 비디오 게임을 한다. 사람들이 그에게 연락하려 할 때가 많지만, 그가 가상 현실 속에서 아무것도 듣지 못하기 때문에 연락할 수 없다. 그가 가상 현실 속에 있을 때는 거의 틀림없이 자신이 가장 좋아하는 게임인 Taktsveðjur를 플레이하고 있다. Taktsveðjur는 검을 휘둘러 나타나는 모든 음표를 맞히려고 하는 게임이며, 흔히 좋은 음악의 리듬에 맞춰 진행된다. 주어진 곡에서 가능한 한 높은 점수를 얻고 최고 기록을 경신하는 데 많은 노력이 들어간다. Atli는 팔을 휘두르고 최고 기록을 경신하느라 너무 바쁘므로, 누군가가 대신 점수를 합산해야 한다!

Taktsveðjur에서는 맞힌 각 음표에 대해 점수를 얻는다. 각 음표의 점수는 $1$점에서 $115$점 사이이며, 음표를 맞히지 못하면 $0$점을 얻는다. 여기에 더해 연속으로 맞힌 음표의 수에 따라 결정되는 점수 배수가 있다. 처음 배수는 $1$이므로, 음표에 정해진 점수만큼 얻는다. 두 음표를 연속으로 맞히면 배수가 $2$이 되고 음표에 정해진 점수의 두 배를 얻는다. 배수가 $2$이고 음표 $4$개를 연속으로 맞히면 배수가 $4$이 된다. 마찬가지로 배수가 $4$이고 음표 $8$개를 연속으로 맞히면 배수가 $8$이 되며, 이는 가능한 가장 높은 배수이다. 어떤 음표를 맞혀 새로운 배수에 도달하면 그 음표부터 새로운 배수가 적용된다. 예를 들어 곡의 첫 두 음표를 맞히면 두 번째 음표부터 이미 두 배의 점수를 얻는다. 음표를 놓치면 배수가 한 단계 낮아져, $8$에서 $4$로, $4$에서 $2$로, 또는 $2$에서 $1$로 바뀐다. 배수가 $1$일 때 음표를 놓치면 $1$로 유지된다.

채점

그룹 | 점수 | 제약 조건

1 | 20 | $1 \leq n \leq 100$, Atli는 어떤 음표도 맞히지 못한다.

2 | 20 | $1 \leq n \leq 100$, Atli는 두 개 이상의 음표를 연속으로 맞히는 일이 없다.

3 | 20 | $1 \leq n \leq 100$, Atli는 어떤 음표도 놓치지 않는다.

4 | 20 | $1 \leq n \leq 100$.

5 | 20 | $1 \leq n \leq 100\,000$.

입력의 첫째 줄에는 Atli가 플레이한 곡의 음표 수를 나타내는 정수 $n$이 주어진다. 다음 $n$개의 줄에는 각각 곡에 있는 음표 하나의 점수가 주어진다. 따라서 각 줄에는 $0 \leq x \leq 115$을 만족하는 정수 $x$ 하나가 주어진다.

Atli가 해당 곡에서 얻는 총점을 출력한다.