ANA is a palindrome

Interview

Time limit1sMemory limit1024 MB

Summary

Count the substrings of S that start and end with A, contain exactly one N, and have no other A.

Level: Easy2 of 10
Topics: String, Brute force
Solved: No attempts yet

Problem

Minyong is a devoted fan of ANA, so he studies all day in the club room even during vacation. He likes ANA because the string ANA is a palindrome, meaning it reads the same forward and backward. Minyong loves ANA so much that he defined a similar ANA string as follows.

A similar ANA string is a string of uppercase English letters with length 3 or more.
A similar ANA string starts and ends with the uppercase letter A, and A does not appear at any other position in the string.
A similar ANA string contains exactly one uppercase letter N.

For example, ARENA and AGENDA are similar ANA strings. However, ANACONDA is not, because it contains three As and two Ns.

Minyong was sad that a string $S$ might not be a similar ANA string. So he tries to find the similar ANA strings among the substrings of $S$ . Given a string $S$ , count how many substrings of $S$ are similar ANA strings.

Input

The first line contains the length $N$ of the string $S$ ( $3\le N\le 100$ ).

The second line contains the string $S$ of length $N$ . $S$ consists of uppercase English letters.

Output

Print the number of substrings of $S$ that are similar ANA strings.

Hint

A substring is a contiguous part of a string.

Examples4

Example 1
Input
```
8
ANACONDA
```
Expected output
```
2
```
Example 2
Input
```
5
ARENA
```
Expected output
```
1
```
Example 3
Input
```
6
AGENDA
```
Expected output
```
1
```

Example 4

Input

40
ANEDUCATEDMINDCANANALYZEANDADAPTTOCHANGE

Expected output