Bessie intenta escribir una cadena de paréntesis equilibrada en su portátil nuevo, pero sus grandes pezuñas la hacen torpe y se equivoca. Encuentra el mínimo número de caracteres a invertir (abrir en cerrar o viceversa) para equilibrarla.

Hay varias definiciones de equilibrio. La más simple exige igual número total de paréntesis de apertura y cierre, y al menos tantos de apertura como de cierre en cualquier prefijo. Estas cadenas están equilibradas:

()
(())
()(()())

Estas no lo están:

)(
())(
((())))

Entrada

• Línea 1: una cadena de paréntesis $A$ de longitud par, como máximo 100,000 caracteres.

Salida

• Línea 1: un entero, el mínimo número de paréntesis que invertir para equilibrar la cadena.

Ejemplos

Entrada 1

())(

Salida 1

2

Nota

Hay que invertir el último y uno de los dos paréntesis de cierre centrales.

Autor: Brian Dean, 2012