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 200\,000~.
• ~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 2\,000~.
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