Bò vụng về

Cho một chuỗi dấu ngoặc độ dài chẵn. Tìm số thao tác đảo tối thiểu (đổi ( thành ) hoặc ngược lại) để chuỗi trở thành chuỗi ngoặc hợp lệ.

Chuỗi ngoặc hợp lệ: số ( bằng số ), và mọi tiền tố đều có số ( $\ge$ số ).

Dữ liệu vào

Một dòng chứa chuỗi dấu ngoặc độ dài $N$ (N chẵn).

Dữ liệu ra

Một số nguyên — số thao tác tối thiểu.

Ràng buộc

• $1\le N\le 100000$, $N$ chẵn.

Ví dụ