| 1 | # We need to make our string alternating, i. e. si≠si+1. When we reverse substring sl…sr, |
| 2 | # we change no more than two pairs sl−1,sl and sr,sr+1. Moreover, one pair should be a |
| 3 | # consecutive pair 00 and other — 11. So, we can find lower bound to our answer as maximum |
| 4 | # between number of pairs of 00 and number of pairs of 11. And we can always reach this |