Dãy ngoặc đúng

Một dãy ngoặc được gọi là dãy ngoặc đúng nếu nó được xây dựng như sau:

• Các dãy ngoặc ()'',[]'', ``{}'' là các dãy ngoặc đúng.

• Nếu \(A\) là dãy ngoặc đúng thì \((A)\), \([A]\), \(\{A\}\) đều là dãy ngoặc đúng.

• Nếu \(A\) và \(B\) đều là dãy ngoặc đúng thì \(AB\) là dãy ngoặc đúng.

Ví dụ: \(([\{\}])\) và \(()\{\}[]\) là các dãy ngoặc đúng, \((()(\) không phải là dãy ngoặc đúng.

Cho một dãy ngoặc \(s\) độ dài \(n\), \(s\) chỉ gồm các dấu ngoặc tròn, vuông, nhọn, mỗi \(s_i \in \{\)(',)', [',]', \{',}'\(\}\), \(1 \le i \le n\). Gọi dãy con liên tiếp \([l, r]\) (\(1 \le l \le r \le n\)) của \(s\) là dãy gồm các dấu ngoặc liên tiếp có độ dài \((r - l + 1)\) được cắt từ dãy \(s\) từ vị trí \(l\) đến vị trí \(r\).

Yêu cầu: Hãy tính số lượng các dãy con liên tiếp của \(s\) là dãy ngoặc đúng.

Input

• Dòng đầu tiên chứa một số nguyên \(n\) (\(1 \le n \le 3 \times 10^5\));

• Dòng thứ hai chứa dãy ngoặc \(s\) độ dài \(n\).

Ràng buộc:

• Có \(30\%\) số điểm thỏa mãn điều kiện \(n \le 100\);

• Có \(20\%\) số điểm thỏa mãn điều kiện \(n \le 1000\);

• Có \(30\%\) số điểm thỏa mãn điều kiện \(n \le 50000\);

• Có \(20\%\) số điểm không có ràng buộc gì thêm.

Output

In ra một số nguyên duy nhất là kết quả của bài toán.

Example 1

Input:

7
)()[](

Output:

3

Example 2

Input:

8
(()[])](

Output:

4

Note

Ở ví dụ thứ nhất, các dãy con liên tiếp là dãy ngoặc đúng gồm: \(s[2..3] = ()\), \(s[4..5] = []\) và \(s[2..5] = ()[]\).

Ở ví dụ thứ hai, các dãy con liên tiếp là dãy ngoặc đúng gồm: \(s[1..6] = (()[])\), \(s[2..3] = ()\), \(s[4..5] = []\) và \(s[2..5] = ()[]\).