Tìm bò

Cho một chuỗi gồm $N$ dấu ngoặc. Đếm số cặp vị trí $(x,y)$ với $x<y$ sao cho chuỗi con tại vị trí $x$ là (( và chuỗi con tại vị trí $y$ là )).

Dữ liệu vào

Một dòng chứa chuỗi dấu ngoặc độ dài $N$.

Dữ liệu ra

Một số nguyên — số cặp $(x,y)$ thỏa mãn.

Ràng buộc

• $1\le N\le 50000$

Ví dụ