JOI 군은 O 도장, X 도장, OX 도장을 각각 \(0\)개 이상 가지고 있다. 이 도장들은 O와 X 표시를 종이에 찍는다. O 도장을 쓰면 O가 하나 찍히고, X 도장을 쓰면 X가 하나 찍힌다. OX 도장을 쓰면 O와 X가 가로로 하나씩 찍히며, 도장 방향을 바꿔 O 오른쪽에 X가 오게 찍을 수도 있고 X 오른쪽에 O가 오게 찍을 수도 있다. JOI 군은 가진 도장을 각각 정확히 한 번씩, 적당한 순서로 써서 종이에 가로로 O와 X를 찍었다. 찍힌 열은 문자열 \(S\)로 나타낸다. \(S\)는 O와 X로 이루어진 길이 \(N\)의 문자열이다. \(S_i\)가 O이면 왼쪽에서 \(i\)번째 표시가 O이고, \(S_i\)가 X이면 X이다 (\(1 \le i \le N\)). JOI 군이 가진 도장 개수는 모르지만, 찍힌 O와 X의 열은 알고 있다. 찍힌 열로부터 JOI 군이 가진 OX 도장 개수로 가능한 값 가운데 최댓값을 구하는 프로그램을 작성하라. |
입력은 다음 형식으로 주어진다.
\(N\)
\(S\)
- 첫째 줄에 문자열의 길이 \(N\)이 주어진다.
- 둘째 줄에 공백 없이 문자열 \(S\)가 한 줄로 주어진다.
- \(1 \le N \le 100000\)
- \(S\)의 각 문자는 O 또는 X이다.
- \(N\)은 정수이다.
다음 형식으로 출력한다.
첫째 줄에 JOI 군이 가진 OX 도장 개수로 가능한 값 가운데 최댓값을 출력한다.
찍힌 표시는 왼쪽부터 O, X, X, O, X이다. O 도장 \(0\)개, X 도장 \(1\)개, OX 도장 \(2\)개를 가지고 다음 순서로 찍으면 된다. 첫 OX 도장으로 O와 X를 이 순서로 찍고, 그 오른쪽에 둘째 OX 도장으로 X와 O를 이 순서로 찍고, 마지막에 X 도장으로 X를 찍는다. OX 도장을 \(3\)개 이상 가진 경우는 있을 수 없으므로 \(2\)를 출력한다.