시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 421 157 139 53.668%

문제

국내 생물학자들은 기존에 보지 못했던 신기한 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+XHJcblxyXG48cD5cclxuXHRcdWM1YjRcdWIyOTAgXHViMGEwLCBcdWM3NzQgXHViZDg0XHVjNzkwXHViOTdjIFx1YzVmMFx1YWQ2Y1x1ZDU1OFx1YjM1OCBcdWQ1NTlcdWM3OTBcdWI0ZTRcdWM3NDAgXHViNDUwIFx1Yzg4NVx1Yjk1OFx1Yzc1OCBcdWIzY2NcdWM1ZjBcdWJjYzBcdWM3NzRcdWI5N2MgXHVjNzdjXHVjNzNjXHVkMGE4XHViMmU0XHViMjk0IFx1YzBhY1x1YzJlNFx1Yzc0NCBcdWM1NGNcdWM1NDRcdWIwYjRcdWM1YzhcdWIyZTQuIFx1Y2NhYiBcdWJjODhcdWM5ZjggXHViM2NjXHVjNWYwXHViY2MwXHVjNzc0XHViMjk0IFx1YmQ4NFx1Yzc5MFx1Yzc1OCBcdWQ1NWMgXHVhZTAwXHVjNzkwXHVhYzAwIFx1YjJlNFx1Yjk3OCBcdWFlMDBcdWM3OTBcdWI4NWMgXHViYzE0XHViMDBjXHViMjk0IFx1YWM4M1x1Yzc3NFx1YjJlNC4gKEEgLSZndDsgQiBcdWI2MTBcdWIyOTQgQiAtJmd0OyBBKSBcdWI0NTAgXHViYzg4XHVjOWY4IFx1YjNjY1x1YzVmMFx1YmNjMFx1Yzc3NFx1YjI5NCBcdWNjYWIgS1x1YWMxYyBcdWFlMDBcdWM3OTBcdWI5N2MgXHViYWE4XHViNDUwIFx1YjJlNFx1Yjk3OCBcdWFlMDBcdWM3OTBcdWI4NWMgXHViYzE0XHVhZmI4XHViMjk0IFx1YWM4M1x1Yzc3NFx1YjJlNDxcL3A+XHJcblxyXG48cD5cclxuXHRETkEgXHViZDg0XHVjNzkwXHVhYzAwIFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1YjNjY1x1YzVmMFx1YmNjMFx1Yzc3NFx1Yjk3YyBcdWNkNWNcdWMxOGMgXHViYTg3IFx1YmM4OCBcdWM3N2NcdWM3M2NcdWQwYTRcdWJhNzQsIFx1YzgwNFx1YmQ4MCBBXHViODVjIFx1YjQxYyBcdWJkODRcdWM3OTBcdWFjMDAgXHViNDE4XHViMjk0XHVjOWMwIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHJcblx0XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWJkODRcdWM3OTBcdWM3NTggXHVhZTM4XHVjNzc0IE5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbGU7IE4gJmxlOyAxLDAwMCwwMDApPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YjQ1OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHViZDg0XHVjNzkwXHViOTdjIFx1Yzc3NFx1YjhlOFx1YjI5NCBOXHVhZTAwXHVjNzkwXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cclxuXHRcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1Y2Q1Y1x1YzE4YyBcdWJhODcgXHViYzg4IFx1YjNjY1x1YzVmMFx1YmNjMFx1Yzc3NFx1Yjk3YyBcdWM3N2NcdWM3M2NcdWQwYTRcdWJhNzQgQVx1Yjg1Y1x1YjljYyBcdWI0MWMgXHViZDg0XHVjNzkwXHVhYzAwIFx1YjQxOFx1YjI5NFx1YzljMCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMjgwNiIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkROQSIsImRlc2NyaXB0aW9uIjoiPHA+QmlvbG9naXN0cyBoYXZlIGRpc2NvdmVyZWQgYSBzdHJhbmdlIEROQSBtb2xlY3VsZSwgYmVzdCBkZXNjcmliZWQgYXMgYSBzZXF1ZW5jZSBvZiBOIGNoYXJhY3RlcnMgZnJvbSB0aGUgc2V0IHtBLCBCfS4gQW4gdW5saWtlbHkgc2VxdWVuY2Ugb2YgbXV0YXRpb25zIGhhcyByZXN1bHRlZCBpbiBhIEROQSBzdHJhbmQgY29uc2lzdGluZyBvbmx5IG9mIEFcdTIwMWZzLiZuYnNwOzxcL3A+XHJcblxyXG48cD5CaW9sb2dpc3RzIGZvdW5kIHRoYXQgdmVyeSBvZGQsIHNvIHRoZXkgYmVnYW4gc3R1ZHlpbmcgdGhlIG11dGF0aW9ucyBpbiBncmVhdGVyIGRldGFpbC5UaGV5IGRpc2NvdmVyZWQgdHdvIHR5cGVzIG9mIG11dGF0aW9ucy4gT25lIHR5cGUgcmVzdWx0cyBpbiBjaGFuZ2luZyBhIHNpbmdsZSBjaGFyYWN0ZXIgb2YgdGhlIHNlcXVlbmNlIChBICZyYXJyOyBCIG9yIEIgJnJhcnI7IEEpLiBUaGUgc2Vjb25kIHR5cGUgY2hhbmdlcyBhIHdob2xlIHByZWZpeCBvZiB0aGUgc2VxdWVuY2UsIHNwZWNpZmljYWxseSByZXBsYWNpbmcgYWxsIGNoYXJhY3RlcnMgaW4gcG9zaXRpb25zIGZyb20gMSB0byBLIChmb3Igc29tZSBLIGJldHdlZW4gMSBhbmQgTiwgaW5jbHVzaXZlKSB3aXRoIHRoZSBvdGhlciBjaGFyYWN0ZXIgKEEgd2l0aCBCLCBCIHdpdGggQSkuPFwvcD5cclxuXHJcbjxwPkNvbXB1dGUgdGhlIGxlYXN0IHBvc3NpYmxlIG51bWJlciBvZiBtdXRhdGlvbnMgdGhhdCBjb3VsZCBjb252ZXJ0IHRoZSBzdGFydGluZyBtb2xlY3VsZSB0byBpdHMgZW5kIHN0YXRlIChjb250YWluaW5nIG9ubHkgQSBjaGFyYWN0ZXJzKS4gTXV0YXRpb25zIGNhbiBvY2N1ciBpbiBhbnkgb3JkZXIuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiBpbnB1dCBjb250YWlucyB0aGUgcG9zaXRpdmUgaW50ZWdlciBOICgxICZsZTsgTiAmbGU7IDEgMDAwIDAwMCksIHRoZSBsZW5ndGggb2YgdGhlIG1vbGVjdWxlLjxcL3A+XHJcblxyXG48cD5UaGUgc2Vjb25kIGxpbmUgb2YgaW5wdXQgY29udGFpbnMgYSBzdHJpbmcgd2l0aCBOIGNoYXJhY3RlcnMsIHdpdGggZWFjaCBjaGFyYWN0ZXIgYmVpbmcgZWl0aGVyIEEgb3IgQi4gVGhpcyBzdHJpbmcgcmVwcmVzZW50cyB0aGUgc3RhcnRpbmcgc3RhdGUgb2YgdGhlIG1vbGVjdWxlLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlRoZSBmaXJzdCBhbmQgb25seSBsaW5lIG9mIG91dHB1dCBtdXN0IGNvbnRhaW4gdGhlIHJlcXVpcmVkIG1pbmltdW0gbnVtYmVyIG9mIG11dGF0aW9ucy48XC9wPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d