Max-Min Operation Difference

You are given a binary string \( s \) of length \( n \) consisting only of characters 0 and 1.

In each operation, you may choose a maximal contiguous substring (i.e. a run) that contains only one type of character and whose length is greater than 1, and change the entire substring to a single character which is the opposite of the original. For example, if \( s = 11001 \), one valid move is to select the leading substring 11 and change it to 0 so that the string becomes 0001 (note that the changed character may merge with adjacent characters), or to select the substring 00 to change it to 1 so that the string becomes 1111.

The operations are performed one after another until no more moves are possible (i.e. when no contiguous substring of identical characters of length > 1 exists, so the string becomes alternating). Different orders of operations may lead to different total numbers of moves being performed. Your task is to compute the difference between the maximum and minimum possible number of operations over all valid sequences.

Important observations:

• Every operation replaces an eligible run (of length \( L \ge 2 \)) with a single character (its opposite), which may merge with its neighbors. In particular, if the chosen run is in the middle of the string (i.e. has both a left and right neighbor), then after flipping the run the new character is equal to both neighbors (since the neighbor characters are necessarily the opposite of the original run’s character), and they will merge. Thus an internal operation reduces the total number of runs by 2, while an operation on a boundary run reduces the number of runs by 1.
• If we denote by \( r \) the number of runs (maximal contiguous segments) in \( s \), then any sequence of operations must eventually merge the runs until the string becomes alternating (or a single character). In fact, if we let \( x \) be the number of boundary operations (reducing runs by 1) and \( y \) be the number of internal operations (reducing runs by 2), then we must have \[ x+y = \text{(total operations)} \quad\text{and}\quad x+2y = r-1. \] It follows that the total number of operations \( m \) is \[ m = x+y = r-1-y. \] Hence, to maximize \( m \) we need to minimize \( y \) (choose as many boundary operations as possible), and to minimize \( m \) we need to maximize \( y \) (choose as many internal operations as possible).
• It turns out that one can show that the maximum possible number of operations is \( m_{\max} = r-1 \) (if all operations are chosen as boundary moves) and the minimum is \( m_{\min} = r-1-\lfloor\frac{r-1}{2}\rfloor \). Therefore, the answer (i.e. the difference between the maximum and minimum number of operations) is \[ \text{Answer} = m_{\max} - m_{\min} = \lfloor\frac{r-1}{2}\rfloor. \]
• Note that if the string is already alternating then no moves can be made. In this case, if we let \( d \) be the number of indices \( i (1 \le i < n) \) with \( s_i \neq s_{i-1} \), then for an alternating string \( d = n-1 \) and the answer will be 0.

In summary, if we let \( d \) be the number of indices \( i (1 \le i < n) \) for which \( s_i \neq s_{i-1} \), then the initial number of runs is \( r = d+1 \) and the answer is given by:

\[ \text{Answer} = \begin{cases} \lfloor\frac{d}{2}\rfloor, & \text{if } d \lt n-1, \ 0, & \text{if } d = n-1. \end{cases} \]

inputFormat

The first line contains an integer \( n \) (\( 1 \le n \le 10^5 \)), the length of the string \( s \).

The second line contains the binary string \( s \) consisting only of characters 0 and 1.

outputFormat

Output a single integer representing the difference between the maximum and minimum number of operations that can be performed.

sample

5
11001

1