Chuỗi nhị phân cân bằng tiền tố (Balanced Binary Prefixes)

Nguồn: Phước Hưng OJ

Phiên bản: Phước Hưng OJ Extended

Đề bài

Cho chuỗi nhị phân gồm đúng n ký tự liền nhau. Khi đọc từ trái qua phải, gặp 1 thì tăng tổng trạng thái 1, gặp 0 thì giảm 1. Đếm các tiền tố không rỗng có tổng đúng bằng 0. Mốc tổng 0 trước khi đọc ký tự đầu tiên không tính; khi n=0, chuỗi rỗng và đáp án 0.

Input

Dòng đầu là n; nếu n>0, dòng tiếp theo là chuỗi đúng n ký tự chỉ gồm 0 và 1. Nếu n=0, không có chuỗi tiếp theo.

Output

In số tiền tố không rỗng có tổng bằng 0.

Subtask

• Subtask 1 (20%): 0 ≤ n ≤ 20.

• Subtask 2 (30%): 0 ≤ n ≤ 1000.

• Subtask 3 (50%): 0 ≤ n ≤ 100000.

Ví dụ

Ví dụ 1

Input:

6
101100

Output:

2

Giải thích: Tổng tiền tố lần lượt 1,0,1,2,1,0; bằng 0 tại vị trí 2 và 6.

Ví dụ 2

Input:

0

Output:

0

Giải thích: Không có tiền tố không rỗng.