시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 1085 454 395 40.722%

문제

십년이면 강산이 변한다.

강산이네 동네에 드디어 극장이 생겼고, 강산이는 극장에 놀러갔다. 매점에서 콜라를 산 뒤, 자리에 앉은 강산이는 큰 혼란에 빠졌다. 양쪽 컵홀더를 이미 옆 사람들이 차지했기 때문에 콜라를 꽂을 컵 홀더가 없었기 때문이다. 영화를 보는 내내 콜라를 손에 들고 있던 강산이는 극장에 다시 왔을 때는 꼭 콜라를 컵 홀더에 놓겠다는 다짐을 한 후 집에 돌아갔다.

극장의 한 줄에는 자리가 N개가 있다. 서로 인접한 좌석 사이에는 컵홀더가 하나씩 있고, 양 끝 좌석에는 컵홀더가 하나씩 더 있다. 또, 이 극장에는 커플석이 있다. 커플석 사이에는 컵홀더가 없다.

극장의 한 줄의 정보가 주어진다. 이때, 이 줄에 사람들이 모두 앉았을 때, 컵홀더에 컵을 꽂을 수 있는 최대 사람의 수를 구하는 프로그램을 작성하시오. 모든 사람은 컵을 한 개만 들고 있고, 자신의 좌석의 양 옆에 있는 컵홀더에만 컵을 꽂을 수 있다.

S는 일반 좌석, L은 커플석을 의미하며, L은 항상 두개씩 쌍으로 주어진다.

어떤 좌석의 배치가 SLLLLSSLL일때, 컵홀더를 *로 표시하면 아래와 같다.

*S*LL*LL*S*S*LL*

위의 예에서 적어도 두 명은 컵을 컵홀더를 사용할 수 없다.

입력

첫째 줄에 좌석의 수 N이 주어진다. (1 ≤ N ≤ 50) 둘쨰 줄에는 좌석의 정보가 주어진다.

출력

컵을 컵홀더에 놓을 수 있는 최대 사람의 수를 출력한다.

예제 입력 1

9
SLLLLSSLL

예제 출력 1

7
W3sicHJvYmxlbV9pZCI6IjI4MTAiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWNlZjVcdWQ2NDBcdWIzNTQiLCJkZXNjcmlwdGlvbiI6IjxwPlxyXG5cdFx1YzJlZFx1YjE0NFx1Yzc3NFx1YmE3NCBcdWFjMTVcdWMwYjBcdWM3NzQgXHViY2MwXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHRcdWFjMTVcdWMwYjBcdWM3NzRcdWIxMjQgXHViM2Q5XHViMTI0XHVjNWQwIFx1YjRkY1x1YjUxNFx1YzViNCBcdWFkZjlcdWM3YTVcdWM3NzQgXHVjMGRkXHVhY2JjXHVhY2UwLCBcdWFjMTVcdWMwYjBcdWM3NzRcdWIyOTQgXHVhZGY5XHVjN2E1XHVjNWQwIFx1YjE4MFx1YjdlY1x1YWMxNFx1YjJlNC4gXHViOWU0XHVjODEwXHVjNWQwXHVjMTFjIFx1Y2Y1Y1x1Yjc3Y1x1Yjk3YyBcdWMwYjAgXHViNGE0LCBcdWM3OTBcdWI5YWNcdWM1ZDAgXHVjNTQ5XHVjNzQwIFx1YWMxNVx1YzBiMFx1Yzc3NFx1YjI5NCBcdWQwNzAgXHVkNjNjXHViNzgwXHVjNWQwIFx1YmU2MFx1Yzg0Y1x1YjJlNC4gXHVjNTkxXHVjYWJkIFx1Y2VmNVx1ZDY0MFx1YjM1NFx1Yjk3YyBcdWM3NzRcdWJiZjggXHVjNjA2IFx1YzBhY1x1Yjc4Y1x1YjRlNFx1Yzc3NCBcdWNjMjhcdWM5YzBcdWQ1ODhcdWFlMzAgXHViNTRjXHViYjM4XHVjNWQwIFx1Y2Y1Y1x1Yjc3Y1x1Yjk3YyBcdWFmNDJcdWM3NDQgXHVjZWY1IFx1ZDY0MFx1YjM1NFx1YWMwMCBcdWM1YzZcdWM1YzhcdWFlMzAgXHViNTRjXHViYjM4XHVjNzc0XHViMmU0LiBcdWM2MDFcdWQ2NTRcdWI5N2MgXHViY2Y0XHViMjk0IFx1YjBiNFx1YjBiNCBcdWNmNWNcdWI3N2NcdWI5N2MgXHVjMTkwXHVjNWQwIFx1YjRlNFx1YWNlMCBcdWM3ODhcdWIzNTggXHVhYzE1XHVjMGIwXHVjNzc0XHViMjk0IFx1YWRmOVx1YzdhNVx1YzVkMCBcdWIyZTRcdWMyZGMgXHVjNjU0XHVjNzQ0IFx1YjU0Y1x1YjI5NCBcdWFmMmQgXHVjZjVjXHViNzdjXHViOTdjIFx1Y2VmNSBcdWQ2NDBcdWIzNTRcdWM1ZDAgXHViMTkzXHVhY2EwXHViMmU0XHViMjk0IFx1YjJlNFx1YzlkMFx1Yzc0NCBcdWQ1NWMgXHVkNmM0IFx1YzlkMVx1YzVkMCBcdWIzY2NcdWM1NDRcdWFjMTRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YWRmOVx1YzdhNVx1Yzc1OCBcdWQ1NWMgXHVjOTA0XHVjNWQwXHViMjk0IFx1Yzc5MFx1YjlhY1x1YWMwMCBOXHVhYzFjXHVhYzAwIFx1Yzc4OFx1YjJlNC4gXHVjMTFjXHViODVjIFx1Yzc3OFx1YzgxMVx1ZDU1YyBcdWM4OGNcdWMxMWQgXHVjMGFjXHVjNzc0XHVjNWQwXHViMjk0IFx1Y2VmNVx1ZDY0MFx1YjM1NFx1YWMwMCBcdWQ1NThcdWIwOThcdWM1MjkgXHVjNzg4XHVhY2UwLCBcdWM1OTEgXHViMDVkIFx1Yzg4Y1x1YzExZFx1YzVkMFx1YjI5NCBcdWNlZjVcdWQ2NDBcdWIzNTRcdWFjMDAgXHVkNTU4XHViMDk4XHVjNTI5IFx1YjM1NCBcdWM3ODhcdWIyZTQuIFx1YjYxMCwgXHVjNzc0IFx1YWRmOVx1YzdhNVx1YzVkMFx1YjI5NCBcdWNlZTRcdWQ1MGNcdWMxMWRcdWM3NzQgXHVjNzg4XHViMmU0LiBcdWNlZTRcdWQ1MGNcdWMxMWQgXHVjMGFjXHVjNzc0XHVjNWQwXHViMjk0IFx1Y2VmNVx1ZDY0MFx1YjM1NFx1YWMwMCBcdWM1YzZcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YWRmOVx1YzdhNVx1Yzc1OCBcdWQ1NWMgXHVjOTA0XHVjNzU4IFx1YzgxNVx1YmNmNFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1Yzc3NFx1YjU0YywgXHVjNzc0IFx1YzkwNFx1YzVkMCBcdWMwYWNcdWI3OGNcdWI0ZTRcdWM3NzQgXHViYWE4XHViNDUwIFx1YzU0OVx1YzU1OFx1Yzc0NCBcdWI1NGMsIFx1Y2VmNVx1ZDY0MFx1YjM1NFx1YzVkMCBcdWNlZjVcdWM3NDQgXHVhZjQyXHVjNzQ0IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVjZDVjXHViMzAwIFx1YzBhY1x1Yjc4Y1x1Yzc1OCBcdWMyMThcdWI5N2MgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuIFx1YmFhOFx1YjRlMCBcdWMwYWNcdWI3OGNcdWM3NDAgXHVjZWY1XHVjNzQ0IFx1ZDU1YyBcdWFjMWNcdWI5Y2MgXHViNGU0XHVhY2UwIFx1Yzc4OFx1YWNlMCwgXHVjNzkwXHVjMmUwXHVjNzU4IFx1Yzg4Y1x1YzExZFx1Yzc1OCBcdWM1OTEgXHVjNjA2XHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWNlZjVcdWQ2NDBcdWIzNTRcdWM1ZDBcdWI5Y2MgXHVjZWY1XHVjNzQ0IFx1YWY0Mlx1Yzc0NCBcdWMyMTggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHRTXHViMjk0IFx1Yzc3Y1x1YmMxOCBcdWM4OGNcdWMxMWQsIExcdWM3NDAgXHVjZWU0XHVkNTBjXHVjMTFkXHVjNzQ0IFx1Yzc1OFx1YmJmOFx1ZDU1OFx1YmE3MCwgTFx1Yzc0MCBcdWQ1NmRcdWMwYzEgXHViNDUwXHVhYzFjXHVjNTI5IFx1YzMwZFx1YzczY1x1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YzViNFx1YjVhNCBcdWM4OGNcdWMxMWRcdWM3NTggXHViYzMwXHVjZTU4XHVhYzAwIFNMTExMU1NMTFx1Yzc3Y1x1YjU0YywgXHVjZWY1XHVkNjQwXHViMzU0XHViOTdjICpcdWI4NWMgXHVkNDVjXHVjMmRjXHVkNTU4XHViYTc0IFx1YzU0NFx1Yjc5OFx1YzY0MCBcdWFjMTlcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdCpTKkxMKkxMKlMqUypMTCo8XC9wPlxyXG5cclxuPHA+XHJcblx0XHVjNzA0XHVjNzU4IFx1YzYwOFx1YzVkMFx1YzExYyBcdWM4MDFcdWM1YjRcdWIzYzQgXHViNDUwIFx1YmE4NVx1Yzc0MCBcdWNlZjVcdWM3NDQgXHVjZWY1XHVkNjQwXHViMzU0XHViOTdjIFx1YzBhY1x1YzZhOVx1ZDU2MCBcdWMyMTggXHVjNWM2XHViMmU0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHJcblx0XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWM4OGNcdWMxMWRcdWM3NTggXHVjMjE4IE5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbGU7IE4gJmxlOyA1MCkgXHViNDU4XHVjYTMwIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWM4OGNcdWMxMWRcdWM3NTggXHVjODE1XHViY2Y0XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cclxuXHRcdWNlZjVcdWM3NDQgXHVjZWY1XHVkNjQwXHViMzU0XHVjNWQwIFx1YjE5M1x1Yzc0NCBcdWMyMTggXHVjNzg4XHViMjk0IFx1Y2Q1Y1x1YjMwMCBcdWMwYWNcdWI3OGNcdWM3NTggXHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIyODEwIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiS0lOTyIsImRlc2NyaXB0aW9uIjoiPHA+TmV3IHRoZWF0ZXIganVzdCBvcGVuZWQgaW4gTWlya28mcnNxdW87cyBob21lIHRvd24sIGFuZCBNaXJrbyBhbmQgU2xhdmtvIG5hdHVyYWxseSB3ZW50IHRvIGNoZWNrIGl0IG91dC4gT3BlbmluZyBwcm9qZWN0aW9uIHdhcyBmaWxsZWQgdG8gdGhlIGxhc3QgcGxhY2UsIGFuZCBNaXJrbyBnb3QgbWFkIGJlY2F1c2UgY3VwLWhvbGRlcnMgYXQgYm90aCBzaWRlcyBvZiBoaXMgc2VhdCB3ZXJlIHRha2VuIGFuZCBoZSBoYWQgbm93aGVyZSB0byBwdXQgaGlzIENva2UuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkEgcm93IGluIHRoZWF0ZXIgaGFzIE4gc2VhdHMuIFRoZXJlIGlzIGEgc2luZ2xlIGN1cC1ob2xkZXIgYmV0d2VlbiBhZGphY2VudCBzZWF0cywgYW5kIGFsc28gdHdvIGFkZGl0aW9uYWwgY3VwLWhvbGRlcnMgYXQgYm90aCBlbmRzIG9mIHRoZSByb3cuIEV4Y2VwdGlvbiB0byB0aGlzIGFyZSBwYWlycyBvZiBsb3ZlIHNlYXRzIC0gdGhlcmUgaXMgbm8gY3VwLWhvbGRlciBiZXR3ZWVuIHRoZW0uJm5ic3A7PFwvcD5cclxuXHJcbjxwPllvdXIgdGFzayBpcyB0byBoZWxwIE1pcmtvLiBHaXZlbiBzZXF1ZW5jZSBvZiBsZXR0ZXJzIGRlc2NyaWJpbmcgc2VhdHMgaW4gc29tZSByb3csIGFuZCBhc3N1bWluZyB0aGF0IGFsbCBzZWF0cyBhcmUgdGFrZW4sIGZpbmQgdGhlIG1heGltdW0gbnVtYmVyIG9mIHBlb3BsZSB0aGF0IGNhbiBwdXQgdGhlaXIgY3VwcyBpbiBhIGN1cC1ob2xkZXIgcmlnaHQgbmV4dCB0byB0aGVpciBzZWF0LiZuYnNwOzxcL3A+XHJcblxyXG48cD5MZXR0ZXIgJmxzcXVvO1MmcnNxdW87IGluIHRoZSBzZXF1ZW5jZSBkZW5vdGVzIG9yZGluYXJ5IHNlYXQsIGFuZCAmbHNxdW87TCZyc3F1bzsgZGVub3RlcyBsb3ZlIHNlYXQuIExvdmUgc2VhdHMgd2lsbCBhbHdheXMgY29tZSBpbiBwYWlycyBvZiBhZGphY2VudCBzZWF0cy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+RGlhZ3JhbSBiZWxvdyBjb3JyZXNwb25kcyB0byBzZXF1ZW5jZSAmbHNxdW87U0xMTExTU0xMJnJzcXVvOywgd2l0aCBhc3Rlcml4ZXMgZGVub3RpbmcgY3VwLWhvbGRlcnMuJm5ic3A7PFwvcD5cclxuXHJcbjxwPiogUyAqIEwgTCAqIEwgTCAqIFMgKiBTICogTCBMICombmJzcDs8XC9wPlxyXG5cclxuPHA+Rm9yIHRoaXMgZXhhbXBsZSwgYXQgbGVhc3QgdHdvIHBlcnNvbnMgd29uJnJzcXVvO3QgYmUgYWJsZSB0byBwdXQgdGhlaXIgY3VwcyBpbnRvIGN1cC1ob2xkZXJzLiZuYnNwOzxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgaW5wdXQgY29udGFpbnMgdGhlIGludGVnZXIgTiAoMSAmbGU7IE4gJmxlOyA1MCksIG51bWJlciBvZiBzZWF0cyBpbiBhIHJvdy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VGhlIGZvbGxvd2luZyBsaW5lIGNvbnRhaW5zIGEgc2VxdWVuY2Ugb2YgTiBsZXR0ZXJzICZsc3F1bztMJnJzcXVvOyBvciAmbHNxdW87UyZyc3F1bzssIGRlc2NyaWJpbmcgdGhlIHJvdyBhcyBzdGF0ZWQgYWJvdmUuJm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+VGhlIGZpcnN0IGFuZCBvbmx5IGxpbmUgb2Ygb3V0cHV0IHNob3VsZCBjb250YWluIHRoZSBtYXhpbXVtIG51bWJlciBvZiBwZW9wbGUgdGhhdCBjYW4gcHV0IHRoZWlyIGN1cHMgaW4gY3VwLWhvbGRlciByaWdodCBuZXh0IHRvIHRoZW0uJm5ic3A7PFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d