시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 1025 425 374 40.608%

문제

십년이면 강산이 변한다.

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

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

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

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

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

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

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

입력

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

출력

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

예제 입력 1

9
SLLLLSSLL

예제 출력 1

7
W3sicHJvYmxlbV9pZCI6IjI4MTAiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWNlZjVcdWQ2NDBcdWIzNTQiLCJkZXNjcmlwdGlvbiI6IjxwPlxyXG5cdFx1YzJlZFx1YjE0NFx1Yzc3NFx1YmE3NCBcdWFjMTVcdWMwYjBcdWM3NzQgXHViY2MwXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHRcdWFjMTVcdWMwYjBcdWM3NzRcdWIxMjQgXHViM2Q5XHViMTI0XHVjNWQwIFx1YjRkY1x1YjUxNFx1YzViNCBcdWFkZjlcdWM3YTVcdWM3NzQgXHVjMGRkXHVhY2JjXHVhY2UwLCBcdWFjMTVcdWMwYjBcdWM3NzRcdWIyOTQgXHVhZGY5XHVjN2E1XHVjNWQwIFx1YjE4MFx1YjdlY1x1YWMxNFx1YjJlNC4gXHViOWU0XHVjODEwXHVjNWQwXHVjMTFjIFx1Y2Y1Y1x1Yjc3Y1x1Yjk3YyBcdWMwYjAgXHViNGE0LCBcdWM3OTBcdWI5YWNcdWM1ZDAgXHVjNTQ5XHVjNzQwIFx1YWMxNVx1YzBiMFx1Yzc3NFx1YjI5NCBcdWQwNzAgXHVkNjNjXHViNzgwXHVjNWQwIFx1YmU2MFx1Yzg0Y1x1YjJlNC4gXHVjNTkxXHVjYWJkIFx1Y2VmNVx1ZDY0MFx1YjM1NFx1Yjk3YyBcdWM3NzRcdWJiZjggXHVjNjA2IFx1YzBhY1x1Yjc4Y1x1YjRlNFx1Yzc3NCBcdWNjMjhcdWM5YzBcdWQ1ODhcdWFlMzAgXHViNTRjXHViYjM4XHVjNWQwIFx1Y2Y1Y1x1Yjc3Y1x1Yjk3YyBcdWFmNDJcdWM3NDQgXHVjZWY1IFx1ZDY0MFx1YjM1NFx1YWMwMCBcdWM1YzZcdWM1YzhcdWFlMzAgXHViNTRjXHViYjM4XHVjNzc0XHViMmU0LiBcdWM2MDFcdWQ2NTRcdWI5N2MgXHViY2Y0XHViMjk0IFx1YjBiNFx1YjBiNCBcdWNmNWNcdWI3N2NcdWI5N2MgXHVjMTkwXHVjNWQwIFx1YjRlNFx1YWNlMCBcdWM3ODhcdWIzNTggXHVhYzE1XHVjMGIwXHVjNzc0XHViMjk0IFx1YWRmOVx1YzdhNVx1YzVkMCBcdWIyZTRcdWMyZGMgXHVjNjU0XHVjNzQ0IFx1YjU0Y1x1YjI5NCBcdWFmMmQgXHVjZjVjXHViNzdjXHViOTdjIFx1Y2VmNSBcdWQ2NDBcdWIzNTRcdWM1ZDAgXHViMTkzXHVhY2EwXHViMmU0XHViMjk0IFx1YjJlNFx1YzlkMFx1Yzc0NCBcdWQ1NWMgXHVkNmM0IFx1YzlkMVx1YzVkMCBcdWIzY2NcdWM1NDRcdWFjMTRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YWRmOVx1YzdhNVx1Yzc1OCBcdWQ1NWMgXHVjOTA0XHVjNWQwXHViMjk0IFx1Yzc5MFx1YjlhY1x1YWMwMCBOXHVhYzFjXHVhYzAwIFx1Yzc4OFx1YjJlNC4gXHVjMTFjXHViODVjIFx1Yzc3OFx1YzgxMVx1ZDU1YyBcdWM4OGNcdWMxMWQgXHVjMGFjXHVjNzc0XHVjNWQwXHViMjk0IFx1Y2VmNVx1ZDY0MFx1YjM1NFx1YWMwMCBcdWQ1NThcdWIwOThcdWM1MjkgXHVjNzg4XHVhY2UwLCBcdWM1OTEgXHViMDVkIFx1Yzg4Y1x1YzExZFx1YzVkMFx1YjI5NCBcdWNlZjVcdWQ2NDBcdWIzNTRcdWFjMDAgXHVkNTU4XHViMDk4XHVjNTI5IFx1YjM1NCBcdWM3ODhcdWIyZTQuIFx1YjYxMCwgXHVjNzc0IFx1YWRmOVx1YzdhNVx1YzVkMFx1YjI5NCBcdWNlZTRcdWQ1MGNcdWMxMWRcdWM3NzQgXHVjNzg4XHViMmU0LiBcdWNlZTRcdWQ1MGNcdWMxMWQgXHVjMGFjXHVjNzc0XHVjNWQwXHViMjk0IFx1Y2VmNVx1ZDY0MFx1YjM1NFx1YWMwMCBcdWM1YzZcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YWRmOVx1YzdhNVx1Yzc1OCBcdWQ1NWMgXHVjOTA0XHVjNzU4IFx1YzgxNVx1YmNmNFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1Yzc3NCBcdWI1NGMsIFx1Yzc3NCBcdWM5MDRcdWM1ZDAgXHVjMGFjXHViNzhjXHViNGU0XHVjNzc0IFx1YmFhOFx1YjQ1MCBcdWM1NDlcdWM1NThcdWM3NDQgXHViNTRjLCBcdWNlZjVcdWQ2NDBcdWIzNTRcdWM1ZDAgXHVjZWY1XHVjNzQ0IFx1YWY0Mlx1Yzc0NCBcdWMyMTggXHVjNzg4XHViMjk0IFx1Y2Q1Y1x1YjMwMCBcdWMwYWNcdWI3OGNcdWM3NTggXHVjMjE4XHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LiBcdWJhYThcdWI0ZTAgXHVjMGFjXHViNzhjXHVjNzQwIFx1Y2VmNVx1Yzc0NCBcdWQ1NWMgXHVhYzFjXHViOWNjIFx1YjRlNFx1YWNlMCBcdWM3ODhcdWFjZTAsIFx1Yzc5MFx1YzJlMFx1Yzc1OCBcdWM4OGNcdWMxMWRcdWM3NTggXHVjNTkxIFx1YzYwNlx1YzVkMCBcdWM3ODhcdWIyOTQgXHVjZWY1XHVkNjQwXHViMzU0XHVjNWQwXHViOWNjIFx1Y2VmNVx1Yzc0NCBcdWFmNDJcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHJcblx0U1x1YjI5NCBcdWM3N2NcdWJjMTggXHVjODhjXHVjMTFkLCBMXHVjNzQwIFx1Y2VlNFx1ZDUwY1x1YzExZFx1Yzc0NCBcdWM3NThcdWJiZjhcdWQ1NThcdWJhNzAsIExcdWM3NDAgXHVkNTZkXHVjMGMxIFx1YjQ1MFx1YWMxY1x1YzUyOSBcdWMzMGRcdWM3M2NcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHRcdWM1YjRcdWI1YTQgXHVjODhjXHVjMTFkXHVjNzU4IFx1YmMzMFx1Y2U1OFx1YWMwMCBTTExMTFNTTExcdWM3N2NcdWI1NGMsIFx1Y2VmNVx1ZDY0MFx1YjM1NFx1Yjk3YyAqXHViODVjIFx1ZDQ1Y1x1YzJkY1x1ZDU1OFx1YmE3NCBcdWM1NDRcdWI3OThcdWM2NDAgXHVhYzE5XHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHQqUypMTCpMTCpTKlMqTEwqPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YzcwNFx1Yzc1OCBcdWM2MDhcdWM1ZDBcdWMxMWMgXHVjODAxXHVjNWI0XHViM2M0IFx1YjQ1MCBcdWJhODVcdWM3NDAgXHVjZWY1XHVjNzQ0IFx1Y2VmNVx1ZDY0MFx1YjM1NFx1Yjk3YyBcdWMwYWNcdWM2YTlcdWQ1NjAgXHVjMjE4IFx1YzVjNlx1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlxyXG5cdFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjODhjXHVjMTFkXHVjNzU4IFx1YzIxOCBOXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEgJmxlOyBOICZsZTsgNTApIFx1YjQ1OFx1Y2EzMCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjODhjXHVjMTFkXHVjNzU4IFx1YzgxNVx1YmNmNFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHJcblx0XHVjZWY1XHVjNzQ0IFx1Y2VmNVx1ZDY0MFx1YjM1NFx1YzVkMCBcdWIxOTNcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWNkNWNcdWIzMDAgXHVjMGFjXHViNzhjXHVjNzU4IFx1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMjgxMCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IktJTk8iLCJkZXNjcmlwdGlvbiI6IjxwPk5ldyB0aGVhdGVyIGp1c3Qgb3BlbmVkIGluIE1pcmtvJnJzcXVvO3MgaG9tZSB0b3duLCBhbmQgTWlya28gYW5kIFNsYXZrbyBuYXR1cmFsbHkgd2VudCB0byBjaGVjayBpdCBvdXQuIE9wZW5pbmcgcHJvamVjdGlvbiB3YXMgZmlsbGVkIHRvIHRoZSBsYXN0IHBsYWNlLCBhbmQgTWlya28gZ290IG1hZCBiZWNhdXNlIGN1cC1ob2xkZXJzIGF0IGJvdGggc2lkZXMgb2YgaGlzIHNlYXQgd2VyZSB0YWtlbiBhbmQgaGUgaGFkIG5vd2hlcmUgdG8gcHV0IGhpcyBDb2tlLiZuYnNwOzxcL3A+XHJcblxyXG48cD5BIHJvdyBpbiB0aGVhdGVyIGhhcyBOIHNlYXRzLiBUaGVyZSBpcyBhIHNpbmdsZSBjdXAtaG9sZGVyIGJldHdlZW4gYWRqYWNlbnQgc2VhdHMsIGFuZCBhbHNvIHR3byBhZGRpdGlvbmFsIGN1cC1ob2xkZXJzIGF0IGJvdGggZW5kcyBvZiB0aGUgcm93LiBFeGNlcHRpb24gdG8gdGhpcyBhcmUgcGFpcnMgb2YgbG92ZSBzZWF0cyAtIHRoZXJlIGlzIG5vIGN1cC1ob2xkZXIgYmV0d2VlbiB0aGVtLiZuYnNwOzxcL3A+XHJcblxyXG48cD5Zb3VyIHRhc2sgaXMgdG8gaGVscCBNaXJrby4gR2l2ZW4gc2VxdWVuY2Ugb2YgbGV0dGVycyBkZXNjcmliaW5nIHNlYXRzIGluIHNvbWUgcm93LCBhbmQgYXNzdW1pbmcgdGhhdCBhbGwgc2VhdHMgYXJlIHRha2VuLCBmaW5kIHRoZSBtYXhpbXVtIG51bWJlciBvZiBwZW9wbGUgdGhhdCBjYW4gcHV0IHRoZWlyIGN1cHMgaW4gYSBjdXAtaG9sZGVyIHJpZ2h0IG5leHQgdG8gdGhlaXIgc2VhdC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+TGV0dGVyICZsc3F1bztTJnJzcXVvOyBpbiB0aGUgc2VxdWVuY2UgZGVub3RlcyBvcmRpbmFyeSBzZWF0LCBhbmQgJmxzcXVvO0wmcnNxdW87IGRlbm90ZXMgbG92ZSBzZWF0LiBMb3ZlIHNlYXRzIHdpbGwgYWx3YXlzIGNvbWUgaW4gcGFpcnMgb2YgYWRqYWNlbnQgc2VhdHMuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkRpYWdyYW0gYmVsb3cgY29ycmVzcG9uZHMgdG8gc2VxdWVuY2UgJmxzcXVvO1NMTExMU1NMTCZyc3F1bzssIHdpdGggYXN0ZXJpeGVzIGRlbm90aW5nIGN1cC1ob2xkZXJzLiZuYnNwOzxcL3A+XHJcblxyXG48cD4qIFMgKiBMIEwgKiBMIEwgKiBTICogUyAqIEwgTCAqJm5ic3A7PFwvcD5cclxuXHJcbjxwPkZvciB0aGlzIGV4YW1wbGUsIGF0IGxlYXN0IHR3byBwZXJzb25zIHdvbiZyc3F1bzt0IGJlIGFibGUgdG8gcHV0IHRoZWlyIGN1cHMgaW50byBjdXAtaG9sZGVycy4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIHRoZSBpbnRlZ2VyIE4gKDEgJmxlOyBOICZsZTsgNTApLCBudW1iZXIgb2Ygc2VhdHMgaW4gYSByb3cuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlRoZSBmb2xsb3dpbmcgbGluZSBjb250YWlucyBhIHNlcXVlbmNlIG9mIE4gbGV0dGVycyAmbHNxdW87TCZyc3F1bzsgb3IgJmxzcXVvO1MmcnNxdW87LCBkZXNjcmliaW5nIHRoZSByb3cgYXMgc3RhdGVkIGFib3ZlLiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlRoZSBmaXJzdCBhbmQgb25seSBsaW5lIG9mIG91dHB1dCBzaG91bGQgY29udGFpbiB0aGUgbWF4aW11bSBudW1iZXIgb2YgcGVvcGxlIHRoYXQgY2FuIHB1dCB0aGVpciBjdXBzIGluIGN1cC1ob2xkZXIgcmlnaHQgbmV4dCB0byB0aGVtLiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==