Một dãy dấu ngoặc hợp lệ là một xâu 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ệ độ sâu 0.
• 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 taọ 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 được xâu dựng 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 sẽ chuyển kí tự ở đầu xâu S xuống cuối 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: Vào từ tập tin văn bản PARENTHESES.INP gồm một dòng chứa xâu S gồm không quá 10⁶ ký tự

Kết quả: Ghi ra tập tin văn bản PARENTHESES.OUT 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.