用户 ainta 有一堆 n 个红球和蓝球。他可以应用某种操作来改变堆叠内球的颜色。
- 当堆栈顶部的球为红色时,将球从堆栈顶部弹出。
- 然后用红色球替换顶部的蓝色球。
- 最后将一些蓝色球推入堆栈,直到堆栈内总共有 n 个球。
如果堆叠内没有蓝色球,ainta 无法应用此操作。给定堆栈的初始状态,ainta 想知道他可以重复应用的最大操作数。
输入
第一行包含一个整数 n (1 ≤ n ≤ 50) — 堆叠内球的数量。
第二行包含一个字符串 s (|s| = n) 描述堆栈的初始状态。字符串 s 的第 i 个字符表示第 i 个球的颜色(我们将从堆栈的顶部到底部对球进行编号)。如果字符是“R”,则颜色为红色。如果字符是“B”,则颜色为蓝色。
输出
打印可以重复应用的最大操作数。
请不要编写 %lld 说明符来读取或写入 С++ 中的 64 位整数。最好使用 cin、cout 流或 %I64d 说明符。
示例
输入 #1
3 RBR
输出 #1
2
输入 #2
4 RBBR
输出 #2
6
输入 #3
5 RBBRR
输出 #3
6
注意
第一个示例如下所示。
用户ainta如何应用第一个操作的说明。他弹出一颗红球,将中间球的颜色从蓝色变为红色,并推入一颗蓝色球。
用户如何应用第二个操作的说明。他不会弹出红球,他只是将顶部球的颜色从蓝色更改为红色。
从现在开始,ainta 无法应用任何操作,因为堆栈内没有蓝色球。 ainta 应用了两次操作,所以答案是 2。
第二个示例如下所示。蓝色箭头表示单个操作。