Монетки

면접 대비

시간 제한1초메모리 제한1024 MB

요약

0과 1로 이루어진 문자열에서 1의 개수에 해당하는 위치의 동전을 뒤집는 과정을 반복할 때, 더 이상 1이 없어질 때까지의 이동 횟수를 구하고 무한 반복이면 -1을 출력한다.

난이도: 보통10점 중 6점
유형: 시뮬레이션, 구현, 배열
정답자: 아직 제출이 없습니다

문제

Пока Мелман сидел в узком ящике и куда-то плыл, ему было очень скучно. Чтобы себя чем-то развлечь, он начал играть в игру с $n$ монетками, которые нашел в ящике.

Он положил монетки перед собой в ряд и пронумеровал их от $1$ до $n$ слева направо. Некоторые монетки лежат вверх решкой, а некоторые --- орлом. Затем, Мелман начинает делать ходы. Для начала, он считает число $k$ --- количество монеток, лежащих орлом вверх. Если таких монет нет, то игра заканчивается. Иначе, он делает ход --- переворачивает монетку номер $k$ .

Помогите Мелману по начальному расположению монеток определить, сколько раз ему придется сделать ход, чтобы закончить игру. Либо сообщите, что игра будет длиться бесконечно долго.

입력

В первой строке дано одно целое число $n$ --- количество монеток ( $1 \le n \le 100\\,000$ ). В следующей строке дана строка из $n$ символов <<0>> и <<1>> --- начальное расположение монеток. Символ <<0>> соответствует монетке, лежащей вверх решкой, а символ <<1>> --- орлом.

출력

Если игра будет длиться бесконечно, выведите <<-1>>. А иначе, выведите количество ходов, которые Мелману придется сделать перед тем, как игра закончится.

예제4

예제 1
입력
```
5
00101
```
예상 출력
```
12
```
예제 2
입력
```
3
101
```
예상 출력
```
4
```
예제 3
입력
```
1
1
```
예상 출력
```
1
```
예제 4
입력
```
5
00000
```
예상 출력
```
0
```