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ự \(\in \{′(′,′)′\}\), 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ệ.

Input

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

Output

• 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ách nào biến đổi xâu \(S\) thành dãy ngoặc hợp lệ, in ra số \(-1\)

Example

))()((() 

2

())()(

1

(()))) 

-1

()()

0