Đoạn con tốt (Good Subarrays)

Nguồn: Codeforces

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

Đề bài

Cho một chuỗi $s$ gồm đúng $n$ chữ số thập phân. Xem mỗi ký tự của $s$ như giá trị số tương ứng.

Một đoạn con liên tiếp $s_l\ldots s_r$ được gọi là tốt nếu tổng các chữ số trong đoạn bằng chính độ dài của đoạn:

Hãy đếm số đoạn con tốt.

Phiên bản nguồn có nhiều test case. Trong Phước Hưng OJ, mỗi file .in chỉ chứa đúng một test case.

Input

• Dòng đầu chứa số nguyên $n$.
• Dòng thứ hai chứa chuỗi $s$ gồm $n$ chữ số.

Output

In số đoạn con tốt của chuỗi.

Subtask

Điều kiện chung đã đối chiếu với nguồn:

• $1\le n\le10^5$

• Chuỗi gồm đúng $n$ chữ số thập phân.

• Nguồn gốc có nhiều test; bản Phước Hưng OJ dùng đúng một test trong mỗi file .in.

• Subtask 1 — 20%: $n\le40$

• Subtask 2 — 30%: $n\le5000$.

• Subtask 3 — 50%: không có điều kiện bổ sung ngoài các điều kiện chung ở trên.

Ví dụ

Input

3
120

Output

3

Giải thích

Với chuỗi 120, có ba đoạn con tốt:

• 1: tổng chữ số là $1$, độ dài là $1$;
• 120: tổng là $1+2+0=3$, độ dài là $3$;
• 20: tổng là $2+0=2$, độ dài là $2$.

Vì vậy kết quả bằng $3$.