Lovro ima posebnu puzlu sačinjenu od zagrada [, (, ] i ). U toj puzli svaka [ zagrada mora biti zatvorena ] zagradom i svaka ( zagrada mora biti zatvorena ) zagradom. Vrste zagrada se ne smiju miješati i sve zagrade moraju biti uparene. Tako string [(]) nije dobra puzla jer se miješaju vrste zagrada i string ][] nije dobar jer zagrada ] nije uparena.

Matematički:

• prazan string je dobra puzla,
• [ + dobra puzla + ] je dobra puzla,
• ( + dobra puzla + ) je dobra puzla,
• dobra puzla + dobra puzla je dobra puzla.

Lovro je davno započeo sastavljati jednu puzlu i sada je želi dovršiti. Nažalost, u međuvremenu je izgubio sve zatvorene zagrade ] i ), ali na sreću ima beskonačno mnogo otvorenih zagrada ( i [.

Budući da puzla može biti jako velika, pomozite Lovri i ispišite koliko najmanje zagrada ( i [ mora dodati u puzlu tako da bude valjana ili ispišite -1 ako je nemoguće dovršiti puzlu. Lovro smije bilo gdje ubacivati zagrade ( i [.

Ulaz

U prvom retku dan je broj \(n\), \((1 \leq n \leq 10^5)\), duljina puzle. U sljedećem retku dan je string od \(n\) znakova, svaki znak je (, ), [ ili ].

Izlaz

U jedan redak ispišite koliko najmanje ( i [ zagrada Lovro treba dodati kako bi dovršio puzlu ili ispišite -1 ukoliko je nemoguće dovršiti puzlu koristeći samo zagrade [ i (.

Primjer ulaza

4
[(])

Primjer izlaza

-1

Primjer ulaza

8
[][](([[

Primjer izlaza

-1

Primjer ulaza

5
)([])

Primjer izlaza

1

Pojašnjenje

Dovoljno je dodati jednu ( zagradu na početak puzle kako bi ona postala dobra.