ABBC

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 중 하나이다.

1. (5점) $ S $의 모든 문자는 A, B 중 하나이다.
2. (20점) $ |S| \le 300 $.
3. (32점) $ |S| \le 1\,000 $.
4. (43점) 추가 제약 조건 없음.

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

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