조용했던 구간의 수

문제

스마트 홈의 소음 감지 장치는 하루 중 정해진 N개의 시간대를 순서대로 관찰한다. 각 시간대의 길이는 같으며, 장치는 관찰 결과를 하나의 문자열 S로 저장한다. 해당 시간대에 집 안이 조용했다면 문자 1을, 조용하지 않았다면 문자 0을 기록한다. 문자열의 첫 번째 문자는 가장 먼저 관찰한 시간대에 해당한다. 집의 관리 프로그램은 이 기록에서 조용한 구간을 모두 찾아 개수를 표시하려고 한다. 하나의 구간은 시작 시간대 L과 끝 시간대 R을 선택하여 정한다. 이때 1 ≤ L ≤ R ≤ N이어야 하며, L번째부터 R번째까지 빠짐없이 포함한다. 선택한 구간에 들어 있는 문자가 전부 1이면 조용한 구간으로 센다. 구간의 길이가 1이어도 조건을 만족하면 하나로 센다. 두 구간은 시작 위치나 끝 위치 중 하나라도 다르면 서로 다른 구간이다. 따라서 서로 겹치는 구간도 각각 셀 수 있다. 예를 들어 기록이 111이면 길이가 1인 구간 세 개, 길이가 2인 구간 두 개, 길이가 3인 구간 한 개가 있어 총 여섯 개이다. 반면 문자 0이 하나라도 들어 있는 구간은 세지 않는다. 관찰 기록의 끝과 처음은 이어져 있지 않다. 마지막 시간대 다음에 첫 번째 시간대가 온다고 생각하여 구간을 만들 수 없으며, 중간의 시간대를 건너뛰어 떨어진 문자들을 하나의 구간으로 묶을 수도 없다. 같은 길이의 조용한 구간이 여러 위치에 있으면 위치마다 별도로 센다. 문자열 S가 주어질 때 조용한 구간의 총개수를 구해야 한다. 기록에 문자 1이 하나도 없다면 답은 0이다. 답은 일반적인 32비트 부호 있는 정수의 최댓값보다 클 수 있다.

입력

첫째 줄에 시간대의 개수 N이 주어진다.
둘째 줄에 길이가 정확히 N인 문자열 S가 주어진다.
1 ≤ N ≤ 100,000이며 N은 정수이다.
S는 문자 0과 1로만 이루어져 있고 공백을 포함하지 않는다.

출력

조용한 구간의 총개수를 정수 하나로 출력한다. 조용한 구간이 없으면 0을 출력한다.

7
1101110

9

4
0000

0

5
11111

15

출처: Devin.KR 자체 제작