Cho xâu \(s\) chỉ gồm ký tự ( và ).Một xâu được gọi là dãy ngoặc đúng khi:

• Xâu rỗng là dãy ngoặc đúng.

• Nếu \(A\) là dãy ngoặc đúng thì (A) là dãy ngoặc đúng.

• Nếu \(A\) và \(B\) là dãy ngoặc đúng thì \(AB\) cũng là dãy ngoặc đúng.

Yêu cầu: Đếm số lượng xâu con gồm các phần tử liên tiếp của xâu s là dãy ngoặc đúng.

Input

• Gồm một dòng chứa xâu s có độ dài không quá \(10^6.\)

Output

• Ghi một số nguyên là số lượng xâu con liên tiếp là dãy ngoặc đúng tìm được.

Ràng buộc

• Subtask 1: 50% test với \(|s|≤100.\)

• Subtask 2: 50% test với \(|s|≤10^6\)

Sample Input

(()(())

Sample Output

4