Bessie vừa mua một chiếc máy tính xách tay mới, nhưng đáng tiếc là cô không thể gõ thành thạo vì móng guốc lớn của cô quá cỡ so với bàn phím nhỏ. Bessie vừa thử gõ một trong những mẫu yêu thích của mình — một chuỗi dấu ngoặc cân bằng. Tuy nhiên, cô nhận ra rằng mình có thể đã gõ nhầm một ký tự, vô tình thay ( bằng ) hoặc ngược lại. Hãy giúp Bessie tính số vị trí trong chuỗi sao cho việc đảo dấu ngoặc duy nhất tại vị trí đó sẽ làm cho toàn bộ chuỗi trở nên cân bằng.

Có nhiều cách để định nghĩa thế nào là một chuỗi dấu ngoặc "cân bằng". Có lẽ định nghĩa đơn giản nhất là tổng số dấu ( phải bằng tổng số dấu ), và trong mọi tiền tố của chuỗi, số dấu ( phải không ít hơn số dấu ). Ví dụ, các chuỗi sau đều cân bằng:

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

trong khi các chuỗi sau thì không:

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

Dữ liệu vào

• Dòng 1 chứa một chuỗi dấu ngoặc có độ dài \(N\) (\(1 \le N \le 100\,000\)).

Dữ liệu ra

• Dòng 1 chứa số vị trí trong chuỗi đầu vào (nếu có) sao cho việc đảo dấu ngoặc tại riêng vị trí đó sẽ làm cho toàn bộ chuỗi trở nên cân bằng.

Ví dụ

()(())))

4

12345678
()(())))

12345678
(((())))

Nguồn

USACO 2012 November Contest, Bronze — Problem 2: Typo

Tác giả đề: Brian Dean, 2012.