시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 329 123 108 55.385%

문제

국내 생물학자들은 기존에 보지 못했던 신기한 DNA 분자를 발견했다. 이 분자는 A와 B로만 이루어진 N글자로 나타낼 수 있다. 이 분자는 계속해서 돌연변이를 한 다음에, A로만 된 분자로 변한다.

어느날, 이 분자를 연구하던 학자들은 두 종류의 돌연변이를 일으킨다는 사실을 알아내었다. 첫 번째 돌연변이는 분자의 한 글자가 다른 글자로 바뀌는 것이다. (A -> B 또는 B -> A) 두 번째 돌연변이는 첫 K개 글자를 모두 다른 글자로 바꾸는 것이다

DNA 분자가 주어졌을 때, 돌연변이를 최소 몇 번 일으키면, 전부 A로 된 분자가 되는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 분자의 길이 N이 주어진다. (1 ≤ N ≤ 1,000,000)

둘째 줄에는 분자를 이루는 N글자가 주어진다.

출력

첫째 줄에 최소 몇 번 돌연변이를 일으키면 A로만 된 분자가 되는지 출력한다.

예제 입력 1

5
BBABB

예제 출력 1

2
W3sicHJvYmxlbV9pZCI6IjI4MDYiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJETkEgXHViYzFjXHVhY2FjIiwiZGVzY3JpcHRpb24iOiI8cD5cclxuXHRcdWFkNmRcdWIwYjQgXHVjMGRkXHViYjNjXHVkNTU5XHVjNzkwXHViNGU0XHVjNzQwIFx1YWUzMFx1Yzg3NFx1YzVkMCBcdWJjZjRcdWM5YzAgXHViYWJiXHVkNTg4XHViMzU4IFx1YzJlMFx1YWUzMFx1ZDU1YyBETkEgXHViZDg0XHVjNzkwXHViOTdjIFx1YmMxY1x1YWNhY1x1ZDU4OFx1YjJlNC4gXHVjNzc0IFx1YmQ4NFx1Yzc5MFx1YjI5NCBBXHVjNjQwIEJcdWI4NWNcdWI5Y2MgXHVjNzc0XHViOGU4XHVjNWI0XHVjOWM0IE5cdWFlMDBcdWM3OTBcdWI4NWMgXHViMDk4XHVkMGMwXHViMGJjIFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1Yzc3NCBcdWJkODRcdWM3OTBcdWIyOTQgXHVhY2M0XHVjMThkXHVkNTc0XHVjMTFjIFx1YjNjY1x1YzVmMFx1YmNjMFx1Yzc3NFx1Yjk3YyBcdWQ1NWMgXHViMmU0XHVjNzRjXHVjNWQwLCBBXHViODVjXHViOWNjIFx1YjQxYyBcdWJkODRcdWM3OTBcdWI4NWMgXHViY2MwXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHRcdWM1YjRcdWIyOTBcdWIwYTAsIFx1Yzc3NCBcdWJkODRcdWM3OTBcdWI5N2MgXHVjNWYwXHVhZDZjXHVkNTU4XHViMzU4IFx1ZDU1OVx1Yzc5MFx1YjRlNFx1Yzc0MCBcdWI0NTAgXHVjODg1XHViOTU4XHVjNzU4IFx1YjNjY1x1YzVmMFx1YmNjMFx1Yzc3NFx1Yjk3YyBcdWM3N2NcdWM3M2NcdWQwYThcdWIyZTRcdWIyOTQgXHVjMGFjXHVjMmU0XHVjNzQ0IFx1YzU0Y1x1YzU0NFx1YjBiNFx1YzVjOFx1YjJlNC4gXHVjY2FiIFx1YmM4OFx1YzlmOCBcdWIzY2NcdWM1ZjBcdWJjYzBcdWM3NzRcdWIyOTQgXHViZDg0XHVjNzkwXHVjNzU4IFx1ZDU1YyBcdWFlMDBcdWM3OTBcdWFjMDAgXHViMmU0XHViOTc4IFx1YWUwMFx1Yzc5MFx1Yjg1YyBcdWJjMTRcdWIwMGNcdWIyOTQgXHVhYzgzXHVjNzc0XHViMmU0LiAoQSAtJmd0OyBCIFx1YjYxMFx1YjI5NCBCIC0mZ3Q7IEEpIFx1YjQ1MCBcdWJjODhcdWM5ZjggXHViM2NjXHVjNWYwXHViY2MwXHVjNzc0XHViMjk0IFx1Y2NhYiBLXHVhYzFjIFx1YWUwMFx1Yzc5MFx1Yjk3YyBcdWJhYThcdWI0NTAgXHViMmU0XHViOTc4IFx1YWUwMFx1Yzc5MFx1Yjg1YyBcdWJjMTRcdWFmYjhcdWIyOTQgXHVhYzgzXHVjNzc0XHViMmU0PFwvcD5cclxuXHJcbjxwPlxyXG5cdEROQSBcdWJkODRcdWM3OTBcdWFjMDAgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHViM2NjXHVjNWYwXHViY2MwXHVjNzc0XHViOTdjIFx1Y2Q1Y1x1YzE4YyBcdWJhODcgXHViYzg4IFx1Yzc3Y1x1YzczY1x1ZDBhNFx1YmE3NCwgXHVjODA0XHViZDgwIEFcdWI4NWMgXHViNDFjIFx1YmQ4NFx1Yzc5MFx1YWMwMCBcdWI0MThcdWIyOTRcdWM5YzAgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cclxuXHRcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YmQ4NFx1Yzc5MFx1Yzc1OCBcdWFlMzhcdWM3NzQgTlx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgTiAmbGU7IDEsMDAwLDAwMCk8XC9wPlxyXG5cclxuPHA+XHJcblx0XHViNDU4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWJkODRcdWM3OTBcdWI5N2MgXHVjNzc0XHViOGU4XHViMjk0IE5cdWFlMDBcdWM3OTBcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlxyXG5cdFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjZDVjXHVjMThjIFx1YmE4NyBcdWJjODggXHViM2NjXHVjNWYwXHViY2MwXHVjNzc0XHViOTdjIFx1Yzc3Y1x1YzczY1x1ZDBhNFx1YmE3NCBBXHViODVjXHViOWNjIFx1YjQxYyBcdWJkODRcdWM3OTBcdWFjMDAgXHViNDE4XHViMjk0XHVjOWMwIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIyODA2IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiRE5BIiwiZGVzY3JpcHRpb24iOiI8cD5CaW9sb2dpc3RzIGhhdmUgZGlzY292ZXJlZCBhIHN0cmFuZ2UgRE5BIG1vbGVjdWxlLCBiZXN0IGRlc2NyaWJlZCBhcyBhIHNlcXVlbmNlIG9mIE4gY2hhcmFjdGVycyBmcm9tIHRoZSBzZXQge0EsIEJ9LiBBbiB1bmxpa2VseSBzZXF1ZW5jZSBvZiBtdXRhdGlvbnMgaGFzIHJlc3VsdGVkIGluIGEgRE5BIHN0cmFuZCBjb25zaXN0aW5nIG9ubHkgb2YgQVx1MjAxZnMuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkJpb2xvZ2lzdHMgZm91bmQgdGhhdCB2ZXJ5IG9kZCwgc28gdGhleSBiZWdhbiBzdHVkeWluZyB0aGUgbXV0YXRpb25zIGluIGdyZWF0ZXIgZGV0YWlsLlRoZXkgZGlzY292ZXJlZCB0d28gdHlwZXMgb2YgbXV0YXRpb25zLiBPbmUgdHlwZSByZXN1bHRzIGluIGNoYW5naW5nIGEgc2luZ2xlIGNoYXJhY3RlciBvZiB0aGUgc2VxdWVuY2UgKEEgJnJhcnI7IEIgb3IgQiAmcmFycjsgQSkuIFRoZSBzZWNvbmQgdHlwZSBjaGFuZ2VzIGEgd2hvbGUgcHJlZml4IG9mIHRoZSBzZXF1ZW5jZSwgc3BlY2lmaWNhbGx5IHJlcGxhY2luZyBhbGwgY2hhcmFjdGVycyBpbiBwb3NpdGlvbnMgZnJvbSAxIHRvIEsgKGZvciBzb21lIEsgYmV0d2VlbiAxIGFuZCBOLCBpbmNsdXNpdmUpIHdpdGggdGhlIG90aGVyIGNoYXJhY3RlciAoQSB3aXRoIEIsIEIgd2l0aCBBKS48XC9wPlxyXG5cclxuPHA+Q29tcHV0ZSB0aGUgbGVhc3QgcG9zc2libGUgbnVtYmVyIG9mIG11dGF0aW9ucyB0aGF0IGNvdWxkIGNvbnZlcnQgdGhlIHN0YXJ0aW5nIG1vbGVjdWxlIHRvIGl0cyBlbmQgc3RhdGUgKGNvbnRhaW5pbmcgb25seSBBIGNoYXJhY3RlcnMpLiBNdXRhdGlvbnMgY2FuIG9jY3VyIGluIGFueSBvcmRlci48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIHRoZSBwb3NpdGl2ZSBpbnRlZ2VyIE4gKDEgJmxlOyBOICZsZTsgMSAwMDAgMDAwKSwgdGhlIGxlbmd0aCBvZiB0aGUgbW9sZWN1bGUuPFwvcD5cclxuXHJcbjxwPlRoZSBzZWNvbmQgbGluZSBvZiBpbnB1dCBjb250YWlucyBhIHN0cmluZyB3aXRoIE4gY2hhcmFjdGVycywgd2l0aCBlYWNoIGNoYXJhY3RlciBiZWluZyBlaXRoZXIgQSBvciBCLiBUaGlzIHN0cmluZyByZXByZXNlbnRzIHRoZSBzdGFydGluZyBzdGF0ZSBvZiB0aGUgbW9sZWN1bGUuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+VGhlIGZpcnN0IGFuZCBvbmx5IGxpbmUgb2Ygb3V0cHV0IG11c3QgY29udGFpbiB0aGUgcmVxdWlyZWQgbWluaW11bSBudW1iZXIgb2YgbXV0YXRpb25zLjxcL3A+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=