Bò Bessie đã trốn thoát và đang ẩn mình trên một sườn đồi phủ đầy cỏ cao. Trong nỗ lực bắt lại Bessie, Farmer John quyết định bò bằng cả tay lẫn đầu gối qua đám cỏ để có thể tiếp cận mà không bị phát hiện. Không may là từ góc nhìn này, ông gặp khó khăn trong việc tìm ra Bessie. Đám cỏ trước mặt Farmer John trông giống như một chuỗi gồm \(N\) dấu ngoặc (\(1 \le N \le 50\,000\)); ví dụ:

)((()())())

Farmer John biết rằng hai chân sau của Bessie trông hệt như một cặp ngoặc mở liền kề ((, còn hai chân trước của cô trông hệt như một cặp ngoặc đóng liền kề )). Vì vậy, vị trí của Bessie có thể được mô tả bởi một cặp chỉ số \(x < y\) sao cho (( xuất hiện tại vị trí \(x\) và )) xuất hiện tại vị trí \(y\). Hãy tính số vị trí khác nhau mà Bessie có thể đang đứng.

Dữ liệu vào

• Dòng 1 chứa một chuỗi dấu ngoặc có độ dài \(N\) (\(1 \le N \le 50\,000\)).

Dữ liệu ra

• Dòng 1 chứa số vị trí mà Bessie có thể đang đứng, tức là số cặp chỉ số phân biệt \(x < y\) sao cho mẫu (( nằm tại chỉ số \(x\) và mẫu )) nằm tại chỉ số \(y\).

Ví dụ

)((()())())

4

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


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


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


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

Nguồn

USACO 2012 November Contest, Bronze — Problem 1: Find the Cow!

Tác giả đề: Brian Dean, 2012.