As the coordinator of Ravi's Stationery Program (RSP), Shaun wants to begin an annual Rock Paper Scissors tournament. Each student picks a move: either Rock (R), Scissors (S), or Paper (P) and line up in a single row.

Shaun then selects a contiguous sequence of students from the line to compete in a Rock, Paper, Scissors tournament, following these rules:

• Shaun chooses any two students who are still in the game to face off. Each student always plays the move they picked at the start.
• The standard rules apply: Rock beats Scissors, Scissors beats Paper, and Paper beats Rock.
• The winner remains in the game, and the loser is eliminated, and leaves the line.
• If the two students choose the same move, the rightmost player is eliminated.

This process continues until only one student remains.

Shaun wants to know how many contiguous sequences of students he can choose so that a "Rock" student ends up as the final winner of the tournament. Remember, Shaun gets to decide who plays in each round.

Input

The first line of the input contains a single integer, ~n~ (~1 \leq n \leq 10^5~), the number of students in RSP.

The second line of the input contains a string of ~n~ characters, each one of R, S, or P, where:

• R means that student will always play rock.
• S means that student will always play scissors.
• P means that student will always play paper.

Output

Output the number of contiguous sequences of students Shaun can choose, so that a student who always plays Rock (R) can be the final winner after they face off.

Example

Input 1

7
RRPSRPP

Output 1

18

Shaun can select the following sequences of students to compete, so that a "Rock" student wins:

Here's an example of how Rock can win if Shaun picks students 2 to 5 (inclusive):

Student 1 (Rock) is the last player left, and wins the tournament.

Note that this is not the only way for Rock to win, nor is Rock guaranteed to win if the match-ups were chosen differently.

Input 2

4
SRRS

Output 2

8

Shaun can select the following sequences of students to compete, so that a "Rock" student wins:

Input 3

5
PRPPS

Output 3

3

Input 4

10
RRRRRRRRRR

Output 4

55