Maximum Operations on ABC String

You are given an integer n and a string s of length n consisting only of the uppercase letters \(\tt{A}\), \(\tt{B}\), and \(\tt{C}\). You can perform the following operation on the string:

Find a substring exactly equal to \(\tt{ABC}\) and replace it with \(\tt{BCA}\). Note that a substring is formed by deleting some (possibly none) characters from the beginning and the end of the string. For example, if \(s=\tt{ABB}\), then \(\tt{A}\), \(\tt{B}\), \(\tt{BB}\), \(\tt{AB}\) and \(\tt{ABB}\) are substrings, whereas \(\tt{ABA}\) is not a substring of \(\tt{ABBA}\).

Determine the maximum number of operations that can be performed on the string if you choose the order of operations optimally.

Any operation performs a left cyclic rotation on the triple \(\tt{ABC}\): \[ \tt{ABC} \to \tt{BCA} \]

It is possible that performing an operation creates a new occurrence of \(\tt{ABC}\) in an overlapping portion of the string. For example, consider \(s = \tt{AABC}\):

• Replace the substring starting at index 1 (i.e. \(\tt{ABC}\)) to get \(\tt{ABCA}\).
• Then, the substring starting at index 0 is \(\tt{ABC}\), which can be replaced to get \(\tt{BCAA}\).

Thus, the maximum number of operations for \(\tt{AABC}\) is 2.

inputFormat

The first line contains an integer \(n\) (with \(1 \le n \le 1000\)).
The second line contains a string s of length \(n\) consisting only of the characters \(\tt{A}\), \(\tt{B}\), and \(\tt{C}\).

outputFormat

Output a single integer, the maximum number of operations that can be performed.

sample

3
ABC

1