404042: GYM101401 F Balloons (A)

Memory Limit:256 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

F. Balloons (A)time limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

There are N balloons linked together in a line. Each balloon is either red, green, or blue. Mr. Light wants to get exactly one balloon of each color (exactly one red balloon, one green balloon, and one blue balloon) - no more or less. Find the minimum number of cuts he has to make to achieve this.

This picture illustrates the first sample test case: "RRGRGRRB". Each letter represents one of the three colors. After making these cuts, Mr. Light will get the two balloons "GR" and the last balloon "B".

Note that the three balloons Mr. Light will get don't have to be disconnected, and it is only allowed to cut the rope that links the balloons together.

Input

The input contains a string S (3 ≤ |S| ≤ 2 × 105), representing the balloons in the line. Each letter is either 'R', 'G', or 'B' and represents the color of that balloon.

It is guaranteed that for each color, there exists at least one balloon with that color.

Output

Print the minimum number of cuts on a single line.

ExamplesInput
RRGRGRRB
Output
3
Input
RGRGBB
Output
2

加入题单

算法标签: