Bessie versucht, auf ihrem neuen Laptop eine ausgeglichene Klammerfolge zu tippen. Ihre großen Hufe machen sie ungeschickt und verursachen Tippfehler. Bestimme die minimale Anzahl umzukehrender Zeichen (öffnende zu schließenden Klammern oder umgekehrt), damit die Folge ausgeglichen wird.

Es gibt mehrere Definitionen. Die einfachste verlangt gleich viele öffnende und schließende Klammern insgesamt und mindestens ebenso viele öffnende wie schließende in jedem Präfix. Folgende Folgen sind ausgeglichen:

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

Diese sind es nicht:

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

Eingabe

• Zeile 1: eine Klammerfolge $A$ gerader Länge mit höchstens 100,000 Zeichen.

Ausgabe

• Zeile 1: eine ganze Zahl, die minimale Anzahl umzukehrender Klammern für eine ausgeglichene Folge.

Beispiele

Eingabe 1

())(

Ausgabe 1

2

Hinweis

Die letzte Klammer und eine der zwei mittleren schließenden müssen umgekehrt werden.

Aufgabenautor: Brian Dean, 2012