题目描述

经过多日的劳作，你几乎已经完成了圣诞集市摊位的布置。只剩下一件事要做：插上那串彩灯。当你插上电线时，你发现自己带错了灯串——你原本计划带一串蓝色灯串，但这些灯却是红色、绿色和蓝色的！绝望中，你靠在摊位上，不小心撞到了一个灯泡，它立即改变了颜色。你注意到，每次触摸一个灯泡，它都会随机呈现三种颜色之一，每种颜色的概率相等。

集市再过五个小时就要开始了，你根本没有足够的时间把这串灯从摊位上拆下来并安装你想要的那一串。至少，你希望所有灯泡都是同一种颜色，无论哪种颜色都可以。你需要触摸灯泡的最小期望次数是多少，才能使所有灯泡变成同一种颜色？

例如，考虑第一个样例输入，假设你触摸红色灯泡直到它变成蓝色。每次触摸它，新颜色可能是红色、绿色或蓝色。直到它变成蓝色所需触摸的期望次数是 $3$。

输入格式

输入包含：

• 一行，一个整数 $n$ ($1 \le n \le 100$)，表示灯串上的灯泡数量。
• 一行，包含 $n$ 个字符，每个字符是 ‘r’、‘g’ 或 ‘b’，表示初始时灯泡的颜色。

输出格式

输出你需要触摸灯泡的期望次数，使得所有灯泡变成同一种颜色，假设你采用最优策略以最小化触摸次数的期望值。

你的答案应具有不超过 $10^{-6}$ 的绝对误差或相对误差。

2
rb

3

3
ggg

0

5
rgbrg

7.5