Tenemos una cadena binaria ~S~ de ~n~ elementos. Usted puede hacer la siguiente operación cualquier número de veces posiblemente 0.

• Selecione un índice ~i~ (~1 \leq i \leq n~) y se le asigna a ~S_i~ la expresión ~1-S_i~.

Encuentre el número mínimo de operaciones tal que la cadena sea no decreciente.

Entrada

La entrada consiste en un número entero ~n~ (~1 \leq n \leq 10^6~) y una cadena ~S~ de tamaño ~n~.

Salida

Un único entero en una línea que representa la respuesta del problema.

Subtareas

• Subtarea 1 (20 puntos): (~1 \leq n \leq 20~).
• Subtarea 2 (40 puntos): (~1 \leq n \leq 10^4~).
• Subtarea 3 (40 puntos): Sin restricciones adicionales.

Ejemplo #1 de Entrada

5
10101

Ejemplo #1 de Salida

2

Ejemplo #2 de Entrada

5
10110

Ejemplo #2 de Salida

2

Explicación: En el primer ejemplo, las secuencias que cumplen la condición son:

00011
00001
01111 
00000
11111  
00111

Una posible respuesta sería ~11111~ con costo 2. Es demostrable que no hay una secuencia válida con costo menor que 2.