Mr Been đang gõ một chuỗi ngoặc đơn cân bằng vào máy tính, nhưng anh hay vụng về và gõ nhầm một số ký tự. Hãy tính số ký tự ít nhất cần đổi chiều (đổi ( thành ) hoặc ngược lại) để chuỗi hiện có trở thành chuỗi cân bằng.

Một chuỗi ngoặc đơn được gọi là cân bằng khi thỏa mãn cả hai điều kiện:

• số dấu ( bằng số dấu );
• với mọi tiền tố của chuỗi, số dấu ( luôn lớn hơn hoặc bằng số dấu ).

Các chuỗi cân bằng, ví dụ:

()
(())
()(()())

Các chuỗi không cân bằng, ví dụ:

)(
())(
((())))

Dữ liệu

• Một chuỗi ngoặc đơn có độ dài tối đa 100.000 ký tự.

Kết quả

• Một số tự nhiên duy nhất: số lượng dấu ngoặc ít nhất phải đổi chiều để chuỗi ban đầu trở thành chuỗi cân bằng.

Ví dụ

CLUMSY.INP

())(

CLUMSY.OUT

2