Tín hiệu là một dãy nhị phân ~n~ bít, các bít được đánh số thứ tự từ 1 đến n. Một đoạn tín hiệu gồm các bít liên tiếp được gọi là chuẩn nếu số lượng bít 0 bằng số lượng bít 1, hai đoạn bít được gọi là khác nhau nếu tồn tại một vị trí thứ tự khác nhau trong tín hiệu bít ban đầu.

Xét ví dụ: ~101011~ sẽ có 6 đoạn tín hiệu chuẩn là:

• ~10~ tính từ vị trí 1 đến vị trí 2.

• ~1010~ tính từ vị trí 1 đến vị trí 4.

• ~01~ tính từ vị trí 2 đến vị trí 3.

• ~0101~ tính từ vị trí 2 đến vị trí 5.

• ~10~ tính từ vị trí 3 đến vị trí 4.

• ~01~ tính từ vị trí 4 đến vị trí 5.

Cho một dãy nhị phân độ dài ~n~. Hãy đếm xem có bao nhiêu tín hiệu chuẩn.

Input

Dòng 1 chứa số nguyên dương ~n~ thỏa ~n \le 10^6~.

Dòng 2 chứa ~n~ bít 0, 1 cách nhau ký tự trắng.

Output

In ra số tín hiệu chuẩn cần tìm.

Constraint

• Subtask 1 (50%): ~n \le 10^3~.

• Subtask 2 (100%): ~n \le 10^5~.

Sample Input

6
1 0 1 0 1 1

Sample Output

6