АЛГОРИТМЫН ЦАГААН ТОЛГОЙ

Нээх, хаах дугуй хаалтуудын хоосон биш дарааллыг зөв, буруу ангилдаг.

Зөв хаалтын дараалал гэдэг нь : "(())()", "()" ба "(()(()))".

Буруу хаалтын дараалал гэдэг нь : ")(", "(()" ба "(()))(".

Өгөгдсөн n ширхэг хаалтуудын дарааллыг ашиглан залгахад зөв дараалал үүсэх хамгийн олон хосын тоог ол. 

Input

Эхний мөрөнд хаалтуудын дарааллын тоо n өгөгдөнө. ( 1<=n<=10⁵ ).

Дараагийн n мөрөнд зөвхөн "(", ")" хаалтуудаас тогтох дараалал өгөгдөнө.

Бүх хаалтуудын дарааллын уртуудын нийлбэр 5 * 10⁵

^{-ээс ихгүй байна.} 

Output

Зөв хаалтын дараалал үүсгэх боломжит хосын тоог ол. 

Example

Input 1:

7
)())
)
((
((
(
)
)

Output 1:

2

Input 2:

4
(
((
(((
(())

Output 2:

0

Input 3:

2
()
(())
Output 3:

 1

4
(
((
(((
(())