Một xâu là dãy ngoặc đúng nếu nó thỏa mãn một trong ba điều kiện sau:

• Nếu ~S~ là xâu rỗng, ~S~ là dãy ngoặc đúng.

• Nếu ~S~ là dãy ngoặc đúng, ~(S)~ cũng là dãy ngoặc đúng.

• Nếu ~A~ và ~B~ là hai dãy ngoặc đúng, việc ghép hai dãy lại thành ~AB~ cũng tạo ra một dãy ngoặc đúng.

Sau đây là ví dụ của một số dãy ngoặc đúng: (), (())(), ((()(()()))).

Một dãy con của một xâu ~S~ bất kỳ là một xâu có thể được tạo thành bằng cách xóa đi một số ký tự (có thể là không xóa ký tự nào, hoặc xóa hết tất cả), và ghép các ký tự còn lại vào với nhau theo thứ tự ban đầu. Ví dụ, abc là dãy con của xâu adbecf, hay ()( là dãy con của xâu ()))(.

Cho một xâu ~S~ có độ dài ~n~, nhiệm vụ của bạn là hãy tìm ra dãy con ~T~ dài nhất của ~S~ sao cho ~T~ là một dãy ngoặc đúng.

Dữ liệu

• Gồm một dòng duy nhất chứa xâu ~S~ có độ dài ~n~ ~(n \le 10^5)~. Các ký tự của xâu đều là ký tự ASCII in được, trừ ký tự khoảng trắng (mã từ 33 tới 126).

Kết quả

• In ra một dòng là độ dài của dãy con ~T~ dài nhất có thể tìm được sao cho ~T~ là một dãy ngoặc đúng.

Điểm số

• Subtask 1 (30%): ~n \le 20~

• Subtask 2 (40%): ~n \le 500~

• Subtask 3 (30%): ~n \le 10^5~

Ví dụ

Sample Input 1

(())

Sample Output 1

4

Sample Input 2

(ab()c()

Sample Output 2

4

Giải thích

Ở test ví dụ 1, ta lấy toàn bộ các ký tự trong xâu ~S~.

Ở test ví dụ 2, ta có 3 cách chọn dãy con tốt nhất, đều với độ dài 4. Sau đây là 4 vị trí ký tự trên xâu ~S~ của 3 cách chọn đó: ~(1, 4, 5, 8); (1, 5, 7, 8); (4, 5, 7, 8)~.