Sửa Dấu Ngoặc

Cho một chuỗi ngoặc $s$ gồm $n$ ký tự mở ngoặc ( và đóng ngoặc ).

Một chuỗi ngoặc được gọi là chuẩn nếu có thể biến đổi chuỗi đó thành một biểu thức số học hợp lệ bằng cách chèn thêm các ký tự 1 và + vào giữa các ký tự ban đầu. Chẳng hạn, các chuỗi ngoặc ()() và (()) là chuẩn (các biểu thức thu được tương ứng là (1)+(1) và ((1+1)+1)), trong khi )( và ( thì không chuẩn.

Bạn được phép đảo loại của một ký tự ngoặc $s_i$, nghĩa là nếu $s_i$ là ) thì đổi thành ( và ngược lại.

Nhiệm vụ của bạn là đếm số lượng vị trí $i$ sao cho sau khi đảo dấu ngoặc ở vị trí thứ $i$, chuỗi ngoặc thu được trở thành một chuỗi ngoặc chuẩn.

Dữ liệu vào

Dòng đầu tiên chứa số nguyên $n$ ($1 ≤ n ≤ 10^6$), biểu thị độ dài của chuỗi ngoặc.

Dòng thứ hai chứa chuỗi $s$ gồm $n$ ký tự, mỗi ký tự là mở ngoặc ( hoặc đóng ngoặc ).

Kết quả

In ra một số nguyên duy nhất, là số lượng vị trí $i$ sao cho khi đảo ký tự ngoặc thứ $i$, chuỗi kết quả trở thành chuỗi ngoặc chuẩn.

Chấm điểm

Subtask 1 (30 points). $n ≤ 5000$

Subtask 2 (70 points). $1 ≤ n ≤ 10^6$

Ví dụ

Input

4
((()

Output

2

Ghi chú

Trong ví dụ mẫu, ta có thể đổi dấu ngoặc tại vị trí $2$ để nhận được ()(), hoặc tại vị trí $3$ để nhận được (()). Cả hai dãy này đều là chuỗi ngoặc chuẩn. Do đó có $2$ vị trí thỏa mãn.