Balanced Binary Prefixes

Source: Phước Hưng OJ

Version: Phuoc Hung OJ Extended

Problem Statement

Read a length-n binary string, adding +1 for 1 and -1 for 0. Count nonempty prefixes whose running sum is zero; do not count the empty prefix.

Input

First n; if n>0, a binary string of exactly n contiguous characters.

Output

Print the number of nonempty zero-sum prefixes.

Subtasks

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

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

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

Examples

Example 1

Input:

6
101100

Output:

2

Explanation: The six prefix sums are 1,0,1,2,1,0: two are zero.

Example 2

Input:

0

Output:

0

Explanation: There are no nonempty prefixes.