모두 앞을 보게 하기

Farmer John이 소 $N$마리 ($1 \le N \le 5000$)를 한 줄로 세웠습니다. 일부 소는 앞을 보고 있지만 나머지는 뒤를 보고 있으며, John은 모든 소가 앞을 보게 만들고 싶습니다.

John에게는 소의 방향을 자동으로 뒤집는 기계가 있습니다. 할인 모델을 산 탓에 이 기계는 하나의 값 $K$ ($1 \le K \le N$)로 영구히 고정되어 있습니다. 기계를 한 번 사용할 때마다 연속한 소 $K$마리의 방향이 반대로 바뀝니다. 앞을 보던 소는 뒤를, 뒤를 보던 소는 앞을 보게 되며, 각 소의 위치는 그대로 유지됩니다. 기계는 $K$마리보다 적은 수에는 작동할 수 없으므로, 줄 안에 완전히 들어가는 정확히 $K$마리의 연속 구간에만 사용할 수 있습니다.

John은 시작하기 전에 하나의 고정된 $K$ 값을 정해야 합니다. 기계로 모든 소가 앞을 보게 만드는 데 필요한 조작 횟수가 최소가 되도록 $K$를 고르고, 그때의 최소 조작 횟수를 $M$이라 합시다. 같은 최소 $M$을 갖는 $K$가 여러 개라면 그중 가장 작은 $K$를 고릅니다.

• 첫째 줄: 정수 $N$.
• 둘째 줄부터 $N+1$번째 줄까지: $i+1$번째 줄에는 문자 하나 F 또는 B가 주어지며, 이는 $i$번 소가 앞(F)을 보는지 뒤(B)를 보는지를 나타냅니다.

공백으로 구분된 두 정수 $K$와 $M$을 출력합니다. $K$는 조작 횟수를 최소로 만드는 값(동점이면 가장 작은 값)이고, $M$은 그 $K$에 대한 최소 조작 횟수입니다.

일곱 마리의 소가 각각 뒤, 뒤, 앞, 뒤, 앞, 뒤, 뒤를 보고 있다고 합시다.

$K = 3$이면 기계를 세 번 사용해야 합니다. 소 $(1,2,3)$, 그다음 $(3,4,5)$, 마지막으로 $(5,6,7)$을 뒤집으면 모든 소가 앞을 보게 됩니다. 아래 그림은 세 번의 조작이 적용되는 동안 각 소의 방향 변화를 보여 줍니다. >는 곧 뒤집힐 소를 나타냅니다.

     B > F   F   F
     B > F   F   F
     F > B > F   F
     B   B > F   F
     F   F > B > F
     B   B   B > F
     B   B   B > F

이 줄에서는 어떤 고정된 $K$로도 세 번보다 적게 끝낼 수 없으므로, 답은 $K = 3$, $M = 3$입니다.