Problema de parcial: Minimizando la cadena

Enunciado del problema

Los estudiantes de Ingeniería de Sistemas están entusiasmados porque lograron ganar la anterior ronda ¿Pero se conformarían con la mitad de la nota y un empate contra los estudiantes de matemáticas? Los anfitriones del curso están seguros de que no, aquí los matemáticos podrían tener la ventaja porque no quieren perder toda su nota.


A los creadores del concurso les llama la atención las cadenas binarias, es decir, cadenas que contienen solamente ceros y unos, y quieren plantear la ronda final del concurso con ellas.


Se les dará una cadena a todos los estudiantes de longitud n y una acción posible. La acción es la siguiente: elegimos dos posiciones adyacentes en la cadena, o lo que es lo mismo, dos caracteres de la cadena seguidos, y si uno de esos dos caracteres contiene 0 y el otro contiene 1, entonces se deben eliminar estos dos dígitos de la cadena, obteniendo una cadena de longitud n - 2 como resultado.


El concurso por el premio mayor es el siguiente: aplicando tantas acciones puedan, ganará el grupo de estudiantes que formen la cadena de menor longitud, siendo esta cadena por supuesto posiblemente de longitud cero ¿Puede ayudarle a su equipo a ganar la siguiente ronda?


A continuación la descripción de todos los ejemplos de entrada y salda, cada acción, es decir, cada cadena a eliminar está marcada con la letra en negrilla:


En la primera entrada (1100) es posible realizar dos acciones de la siguiente manera:
1 10 0 -> 10 -> cadena vacía

En la segunda entrada (01010) es posible realizar dos acciones de la siguiente manera:

01 010 -> 01 0 -> 0

En la tercera entrada (11101111) es posible realizar solamente una acción de la siguiente manera:

111 01 111 -> 111111


Entrada

La entrada está compuesta por dos elementos separados por un salto de linea.


El primer elemento es la longitud de la cadena de entrada n con la siguiente restricción 0 <= n <= 10000.


El segundo elemento es la cadena binaria a minimizar en donde cada carecter c tiene la siguiente restriccion 0 <= c <= 1 y la longitud de la cadena es n como se describió en la anterior línea.


Salida

Su programa deberá imprimir el número ganador, es decir, la longitud mínima de la cadena resultante después de aplicar la acción tantas veces sea posible.


Ejemplos


Entrada Ejemplo 1

4
1100

Salida Ejemplo 1

0

Entrada Ejemplo 2

5
01010

Salida Ejemplo 2

1

Entrada Ejemplo 3

8
11101111

Salida Ejemplo 3

6

Notas

La salida debe tener un caracter de nueva línea al final del archivo, de lo contrario puede recibir el veredicto de respuesta incorrecta.



Seleccione el lenguaje