背景

• Idea: USACO
• Data: USACO
• Solution: USACO
• 题面: USACO
• Translate: oistream

本题来自 USACO 1.2 Greedy Gift Givers

描述

You have a necklace of \(N\) red, white, or blue beads (\(3\leq N\leq 350\)) some of which are red, others blue, and others white, arranged at random. Here are two examples for \(N=29\):

你有一个含有 \(N\) 个珠子的项链，每个珠子可能是红色、蓝色或白色的，这三种颜色的珠子在项链上无规律排列。下图是两个 \(N=29\) 时可能的项链。

The beads considered first and second in the text that follows have been marked in the picture.

图片中用文本标记了项链的第一个和第二个珠子。

The configuration in Figure \(\text{A}\) may be represented as a string of b's and r's, where b represents a blue bead and r represents a red one, as follows: brbrrrbbbrrrrrbrrbbrbbbbrrrrb .

图片 \(\text{A}\) 中的项链可以转化成一个由字符 b 和 r 组成的字符串，其中一个 b 代表一个蓝色珠子，一个 r 代表一个红色珠子，转化成的字符串是 brbrrrbbbrrrrrbrrbbrbbbbrrrrb。

Suppose you are to break the necklace at some point, lay it out straight, and then collect beads of the same color from one end until you reach a bead of a different color, and do the same for the other end (which might not be of the same color as the beads collected before this).

假设你要在一个点断开这个项链，将项链变为一条直线。然后从项链的一端开始，一个一个的收集珠子，直到遇到一个和目前收集的颜色不同的珠子。然后从另一端开始，按照同样的方法收集珠子（但这次收集到的珠子的颜色可能和上次不同），直到遇到一个不同颜色的珠子。

Determine the point where the necklace should be broken so that the most number of beads can be collected.

计算出一个断开项链的点，使得从这个点断开之后按照上述方法收集到的珠子数最大。

In some necklaces, white beads had been included as shown in Figure \(\text{B}\) above. When collecting beads, a white bead that is encountered may be treated as either red or blue and then painted with the desired color. The string that represents this configuration can include any of the three symbols r, b and w.

一些项链 （例如上图 \(\text{B}\) ）可能含有白色珠子。当在收集珠子的时候遇到一个白色珠子时，可以将其变为你想要的任意颜色。 代表项链的字符串可以包含三个字符，r，b 和 w。

Write a program to determine the largest number of beads that can be collected from a supplied necklace.

给定一个（用字符串表示的）项链，你需要写一个程序，计算出按照上述方法任意选点断开项链，能收集到的最大的珠子数目。

输入格式

Line \(1\): \(N\), the number of beads

第一行为 \(N\)，即珠子数目。

Line 2: a string of \(N\) characters, each of which is r, b, or w

第二行为一个包含 \(N\) 个字符的字符串，此字符串仅包含字符 r，b，w。

输出格式

A single line containing the maximum of number of beads that can be collected from the supplied necklace.

输出有一行，为能收集到的最大珠子数。

样例

输入样例1

29
wwwbbrwrbrbrrbrbrwrwwrbwrwrrb

输出样例1

11

样例解释

样例解释-图片

For example, for the necklace in Figure \(\text{A}\), \(8\) beads can be collected, with the breaking point either between bead \(9\) and bead \(10\) or else between bead \(24\) and bead \(25\).

以图 \(\text{A}\) 所示的项链为例，当在第 \(9\) 颗珠子和第 \(10\) 颗珠子之间或在第 \(24\) 颗珠子和第 \(25\) 颗珠子之间断开项链时，收集到的珠子数目取最大值 \(8\)。

样例解释1

Consider two copies of the beads (kind of like being able to runaround the ends). The string of \(11\) is marked.

将项链复制一份（就是破环成链——译注）。最大值为 \(11\)，如图所示。

数据规模与约定

对于全部数据，\(3\leq N\leq 350\)。