동그라미 엑스 스탬프
면접 대비시간 제한2초메모리 제한512 MB
원과 십자, 그리고 두 방향으로 찍는 원 십자 도장으로 만든 O와 X 문자열이 주어질 때, 원 십자 도장 개수의 최댓값을 구합니다.
문제
JOI 군은 동그라미 스탬프, 엑스 스탬프, 동그라미 엑스 스탬프의 3종류 스탬프를 각각 0개 이상 가지고 있다. 이들은 동그라미나 엑스 표시를 종이에 찍을 수 있는 스탬프이다.
동그라미 스탬프를 사용하면 동그라미가 1개 찍히고, 엑스 스탬프를 사용하면 엑스가 1개 찍힌다. 동그라미 엑스 스탬프를 사용하면 동그라미와 엑스가 가로로 한 줄에 1개씩 찍히며, 스탬프의 방향을 바꾸어 동그라미 오른쪽에 엑스가 오게 할 수도, 엑스 오른쪽에 동그라미가 오게 할 수도 있다.
JOI 군은 가지고 있는 스탬프를 각각 정확히 1번씩 적당한 순서로 사용해 종이에 동그라미와 엑스를 가로로 한 줄로 찍었다. 찍힌 동그라미와 엑스의 나열은 문자열 S로 나타난다. S는 O와 X로 구성된 길이 N의 문자열이고, S_i = O이면 JOI 군이 찍은 표시 중 왼쪽에서 i번째 것이 동그라미임을 나타내며, S_i = X이면 그것이 엑스임을 나타낸다 (1 ≤ i ≤ N).
당신은 JOI 군이 가지고 있는 스탬프의 개수는 알지 못하지만, JOI 군이 찍은 동그라미와 엑스의 나열은 알고 있다. 찍힌 동그라미와 엑스의 나열로부터, JOI 군이 가지고 있는 동그라미 엑스 스탬프의 개수로 가능한 값 중 최댓값을 구하라.
입력
입력은 다음 형식으로 표준 입력에서 주어진다.
N
S
출력
JOI 군이 가지고 있는 동그라미 엑스 스탬프의 개수로 가능한 값 중 최댓값을 출력하라.
제한
- 1 ≤ N ≤ 100000 (= 10^5)
- S는 길이 N의 문자열이다.
- S의 각 문자는 O 또는 X이다.