圆周上有 $2N$ 个点，按顺时针方向编号为 $1$ 到 $2N$。每个点要么是白色，要么是黑色。其中有 $N$ 个白点和 $N$ 个黑点。

我们将绘制 $N$ 条线段连接这些点，使得满足以下条件： 每个点恰好是一条线段的端点。 每条线段连接一个白点和一个黑点。

在 $N$ 条线段中，相交的线段对数称为交点数。编写一个程序，在给定点颜色信息的情况下，计算绘制 $N$ 条线段时交点数的最大值。

输入格式

从标准输入读取以下数据。

$N$ $S$

其中 $S$ 是一个长度为 $2N$ 的字符串，表示点的颜色。$S$ 中的每个字符要么是 B，要么是 W。第 $i$ 个字符（$1 \le i \le 2N$）表示第 $i$ 个点的颜色。如果是 B，则该点为黑色；如果是 W，则该点为白色。

输出格式

输出一行到标准输出。输出应包含满足条件时绘制 $N$ 条线段所能得到的最大交点数。

数据范围

• $1 \le N \le 200\,000$。
• $S$ 是一个由 B 和 W 组成的长度为 $2N$ 的字符串。字符 B 在字符串 $S$ 中出现 $N$ 次，字符 W 在字符串 $S$ 中出现 $N$ 次。

子任务

1. (4 分) $N \le 8$。
2. (21 分) $N \le 300$。
3. (10 分) $N \le 2\,000$。
4. (65 分) 无附加限制。

样例

样例输入 1

3
BBWWBW

样例输出 1

2

说明：如果按照左侧图形绘制线段，则交点数为 2。另一方面，如果按照右侧图形绘制线段，则交点数为 3，但不满足题目描述中的条件。

样例输入 2

5
BWBWBBWBWW

样例输出 2

8

样例输入 3

10
WBBBWBBWWBWWBWWBWBWB

样例输出 3

41

样例输入 4

16
WWWBWBBBBWWBWWBWWBBWWBBBWBBBWWBW

样例输出 4

105