FIND THE COW!

Cô bò Bessie đã trốn thoát và đang trốn ở một đồi núi với những đồng cỏ cao. Nông dân John (FJ), người đang muốn tìm kiếm Bessie, đã quyết định bò trên đồng cỏ bằng tay và đầu gối để tìm ra dấu vết của Bessie. Không may thay, ông ta có một chút vấn đề với việc tìm kiếm Bessie: Dãy cỏ ở trước mặt FJ trông như một chuỗi ngoặc đơn có độ dài N (1≤ N≤ 50,000); ví dụ: )((()())()) FJ biết rằng chân sau của Bessie giống như một cặp dấu mở ngoặc đơn ((, và chân trước của cô ta giống như một cặp dấu đóng ngoặc đơn )). Vị trí của Bessie có thể được diễn tả bởi một cặp x < y , trong đó (( được tìm ở vị trí x, và )) được tìm ở vị trí y. Hãy đếm có bao nhiêu vị trí mà Bessie có thể đang đứng.

Dữ liệu vào: ghi từ tệp COWFIND.INP

+ Dòng 1: Một chuỗi ngoặc đơn có độ dài là N

Dữ liệu ra: ghi vào tệp văn bản COWFIND.OUT một số nguyên cho biết vị trí Bessise đang đứng

Ví dụ:

COWFIND.INP	COWFIND.OUT
)((()())())	4

Giải thích: Các vị trí Bessise có thể đứng là

1. )((()())())

2. )((()())())

3. )((()())())

4. )((()())())

TEST