A, B, C로만 이루어졌고 길이가 |S|인 문자열 S가 있다. 당신은 이 문자열에 다음과 같은 시행을 할 수 있다.

• A와 그 뒤에 있는 B를 지운다.
• B와 그 뒤에 있는 C를 지운다.

각 문자는 최대 한 번만 지울 수 있다.

예를 들어 ABCBA를 보자. 각 문자에 왼쪽부터 1번, 2번, 3번. . . 과 같이 번호를 붙이면 다음과 같이 시행할 수 있다.

• 1번 A와 2번 B를 지운다. 이 경우 시행의 횟수는 1번이고, 남은 문자열은 CBA이다. 어떤 두 문자를 골라도 시행의 조건을 만족시킬 수 없으므로, 더 이상 시행을 할 수 없다.
• 1번 A와 4번 B를 지우고, 이어 2번 B와 3번 C를 지운다. 이 경우 시행의 횟수는 2번이고 남은 문자열은 A이다. 문자열에 남은 문자가 하나이므로, 더 이상 시행을 할 수 없다.

이외에도 시행을 할 수 있는 여러 경우의 수가 있다.

시행을 할 수 있는 최대 횟수를 구해라.

• \(1 \le |S| \le 300\,000\)
• \(S\)의 모든 문자는 A, B, C 중 하나이다.

첫 번째 줄에 문자열 S가 주어진다.

첫 번째 줄에 답을 출력한다.

riseoj 작성

출처 올림피아드 > 한국정보올림피아드 > KOI 2022 > 1차 대회 > 고등부 2번