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, umeđ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 to nije moguće.

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.