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

Бэсси үнээ дөнгөж саяхан шинэ нөүтбүүк худалдан авчээ. Гэвч тэр товчлуурандаа хэтэрхий томдсон туурайнаасаа болоод сайн бичиж чаддаггүйгээ олж мэджээ. Түүний хамгийн дуртай бичвэр бол зөвхөн хаалтуудаас тогтсон тэнцвэртэй тэмдэгт мөр юм. Тэр үүнийг бичих гэж оролдохдоо алдаж зарим нэг хаалтыг буруу харуулж бичсэн байх магадлалтайгаа ойлгожээ. Таны даалгавар бол Бэссигийн бичсэн мөрний сонгосон нэг хаалтыг эсрэг тийш нь харуулахад тэмдэгт мөр зөв болох боломжит ялгаатай хаалтуудын тоог олох явдал юм. “Тэнцвэртэй” гэдэг нь энгийнээр “(“ болон “)” -ийн тоо тэнцүү байх ёстой буюу хаалтнууд зөв байна гэсэн үг. Жишээ нь:

( )

( ( ) )

( ) ( ( ) ( ) ) нар нь тэнцвэртэй хаалт байхад

) (
( ) ) (
( ( ( ) ) ) ) нар нь тэнцвэргүй хаалтнууд болно.

Input

N урттай А тэмдэгт мөр ( 1 <= N <= 100000 ).

Output

Боломжит хаалтнуудын тоо болох ганц тоо.

Example

Input:

( ) ( ( ) ) ) )

Output:

4

Тайлбар :

Тэмдэгт мөрийн элемэнтүүдийг дугаарлавал

1 2 3 4 5 6 7 8

(  )  (  (  )  )  )  ) болно. Эндээс харахад бид хаалтнуудыг тэнцвэртэй болгохын тулд 2,5,6,7-р хаалтуудыг сольж болно. Иймд нийт боломжны тоо 4 болно.

Орчуулсан : УБ 1-р сургууль Э.Энхтүшиг