Successful String

Interview

Time limit1sMemory limit1024 MB

Summary

Count substrings of a given string that contain at least one pair of equal adjacent characters.

Level: Medium4 of 10
Topics: String, Combinatorics, Math, Implementation
Solved: No attempts yet

Problem

Yunee is studying English vocabulary. Among the many words Yunee has learned, "success" is Yunee's favorite word and "failure" is Yunee's least favorite word.

Yunee noticed that two identical characters appear in a row in the word "success" but not in the word "failure." So Yunee decided to call a string a "successful string" when it has the property of the word "success." Formally, a string $S$ is a successful string when there is a position $i$ such that $S_i = S_{i+1}$ . Here $S_i$ denotes the $i$ -th character of $S$ .

Yunee wants to count how many successful strings there are among the substrings of a given string. Write a program that counts the number of successful substrings. You have to consider two substrings distinct when their positions are different, even if the two strings are the same.

Input

The first line contains an integer $N$ that represents the length of a string. $(1 \leq N \leq 10^6)$

The second line contains a string of length $N$ consisting of lowercase alphabets.

Output

Output the number of successful strings among the substrings of the given string.

Examples3

Example 1
Input
```
7
success
```
Expected output
```
15
```
Example 2
Input
```
7
failure
```
Expected output
```
0
```
Example 3
Input
```
4
aaaa
```
Expected output
```
6
```