Ngoặc Chuẩn

Một dãy ngoặc được gọi là chuẩn nếu ta có thể tạo ra một biểu thức số học đúng quy cách bằng cách chèn các ký tự + và 1 vào dãy đó. Ví dụ, các dãy (())(), () và (()(())) là chuẩn, trong khi )(, (() và (()))( không phải là dãy chuẩn.

Một kỹ sư phần mềm đang xử lý một dãy ký tự ngoặc và muốn xóa bớt một số ký tự sao cho phần còn lại tạo thành một dãy ngoặc chuẩn. Hãy tìm độ dài lớn nhất của một dãy ngoặc chuẩn có thể thu được sau khi xóa.

Dữ liệu vào

Dòng duy nhất chứa chuỗi ký tự $s$ không rỗng ($1 ≤ |{}s|{} ≤ 10^6$), chỉ bao gồm các ký tự ( và ).

Kết quả

In ra một số nguyên duy nhất là độ dài lớn nhất của một dãy ngoặc chuẩn có thể thu được.

Chấm điểm

Subtask 1 (20 points). $|s| ≤ 20$

Subtask 2 (30 points). $|s| ≤ 4000$

Subtask 3 (50 points). 1 $≤ |{}$s| $≤ 10^6$

Ví dụ

Input

)(()

Output

2

Ghi chú

Trong ví dụ mẫu, ta có thể xóa ký tự đầu tiên và một ký tự mở ngoặc để thu được chuỗi chuẩn (), có độ dài là $2$.