Sắp xếp lại dãy ngoặc

Cho một dãy ngoặc $s$ độ dài $n$, chỉ gồm các ký tự ( và ).

Một dãy ngoặc được gọi là đúng (hợp lệ) nếu có thể chèn các ký tự + và 1 để biến nó thành một biểu thức số học hợp lệ. Ví dụ: (())(), (), (()(())) là các dãy đúng; còn )(, ((), (()))( thì không.

Bạn được phép thực hiện thao tác sắp xếp lại sau nhiều lần tuỳ ý (kể cả $0$):

• Chọn một đoạn con liên tiếp của $s$, độ dài $\ell$, rồi sắp xếp lại các ký tự trong đoạn đó theo thứ tự bất kỳ. Thao tác này tốn $\ell$ đơn vị thời gian.

Lưu ý rằng thao tác này không thay đổi tổng số ký tự ( và ) trong $s$.

Hãy tính tổng thời gian nhỏ nhất để biến $s$ thành một dãy ngoặc đúng, hoặc xác định rằng điều đó là không thể.

Dữ liệu vào

• Dòng đầu chứa số nguyên $n$ — độ dài của $s$.
• Dòng thứ hai chứa xâu $s$ độ dài $n$, chỉ gồm các ký tự ( và ).

Dữ liệu ra

Một số nguyên duy nhất — tổng thời gian nhỏ nhất, hoặc $-1$ nếu không thể.

Ràng buộc

• $1\le n\le {10}^6$.

Ví dụ