Một dãy dấu ngoặc hợp lệ là một xâu các ký tự ~(~ và ~)~ được định nghĩa như sau:

• Xâu rỗng là một dãy dấu ngoặc hợp lệ
• Nếu ~A~ là dãy dấu ngoặc hợp lệ thì ~(A)~ là dãy dấu ngoặc hợp lệ
• Nếu ~A~ và ~B~ là hai dãy dấu ngoặc hợp lệ thì ~AB~ (xâu tạo thành bằng cách ghép xâu ~A~ với xâu ~B~) là dãy dấu ngoặc hợp lệ.

Những xâu không xây dựng được theo các quy tắc trên không phải là dãy dấu ngoặc hợp lệ.

Ví dụ: ~((()()))~ và ~()()()~ là những dãy ngoặc hợp lệ, ~)()(~ và ~((())~ không phải là dãy ngoặc hợp lệ.

Yêu cầu:

Cho xâu ký tự ~S~ chỉ gồm các ký tự ~∈ \{~(~,~ )~\}~, người ta cho phép bạn thực hiện (~0~ hoặc một số) phép biến đổi, mỗi phép biến đổi thuộc một trong hai dạng:

• Chuyển ký tự ở đầu xâu ~S~ xuống cuối xâu
• Chuyển ký tự ở cuối xâu ~S~ lên đầu xâu

Hãy tìm cách dùng ít phép biến đổi nhất để biến xâu ~S~ thành một dãy dấu ngoặc hợp lệ

Dữ liệu:

Xâu ~S~ gồm không quá ~10^6~ ký tự ~∈ \{~(~,~ )~\}~

Kết quả:

Ghi ra một số nguyên duy nhất là số phép biến đổi cần sử dụng, nếu không có các nào biến đổi xâu ~S~ thành dãy ngoặc hợp lệ, in ra số ~-1~

Sample 1

Input

))()((()

Output

2

Sample 2

Input

())()(

Output

1

Sample 3

Input

(())))

Output

-1

Sample 4

Input

()()

Output

0