There are $2N$ points on a circle numbered from $1$ through $2N$, in clockwise order. Each point is either white or black. There are $N$ white points and $N$ black points.

We will draw $N$ line segments connecting these points so that the following conditions are satisfied.

• Each point is an end point of exactly one line segment.
• Each line segment connects a white point and a black point.

Among the $N$ line segments, the number of pairs of line segments intersecting each other is called the intersection number. Write a program which, given the information of the colors of the points, calculates the maximum of the intersection number when we draw $N$ line segments.

Input Specification

Read the following data from the standard input.

$N$

$S$

Here $S$ is a string of length $2N$ representing the colors of the points. Each character of $S$ is either B or W, and the $i$-th character $(1\le i\le 2N)$ is the color of the $i$-th point. It is B if the point is black, and W if the point is white.

Output Specification

Write one line to the standard output. The output should contain the maximum of the intersection number when we draw $N$ line segments satisfying the conditions.

Constraints

• $1\le N\le 200000$.
• $S$ is a string of length $2N$ which consists of B and W. The character B appears $N$ times in the string $S$, and the character W appears $N$ times in the string $S$.

Subtasks

1. (4 points) $N\le 8$.
2. (21 points) $N\le 300$.
3. (10 points) $N\le 2000$.
4. (65 points) No additional constraints.

Sample Input 1

3
BBWWBW

Sample Output 1

2

Explanation for Sample 1

If we draw line segments as in the figure on the left, then the intersection number is $2$. On the other hand, if we draw line segments as in the figure on the right, then the intersection number is $3$, but the conditions in the task statement are not satisfied.

Sample Input 2

5
BWBWBBWBWW

Sample Output 2

8

Sample Input 3

10
WBBBWBBWWBWWBWWBWBWB

Sample Output 3

41

Sample Input 4

16
WWWBWBBBBWWBWWBWWBBWWBBBWBBBWWBW

Sample Output 4

105