#2752 BOJ 거리

18  1 s   128 MB  

Description

BOJ 거리(Street)는 보도블럭 N개가 일렬로 놓인 형태의 도로이다. 도로의 각 보도블럭은 1번부터 N번까지 차례로 번호가 매겨져 있다.
 
‘스타트’의 집은 1번에 있고, ‘링크’의 집은 N번에 있다. 스타트는 링크를 만나기 위해서 각 보도블럭을 점프하여 가려고 한다.
 
BOJ 거리의 각 보도블럭에는 B, O, J 중 하나의 알파벳이 그려져 있다. 단, 1번 보도블럭은 반드시 B가 그려져있다.
 
스타트는 점프를 통해 다른 보도블럭으로 이동할 수 있다. 이 때, 항상 번호가 증가하는 방향으로 점프를 해야한다.
 
만약 스타트가 현재 있는 보도블럭이 i번 보도블럭이라면, [i+1, N]사이의 번호를 가지는 보도블럭으로 점프할 수 있다.
 
한 번 k칸 만큼 점프를 하는데 필요한 에너지의 양은  (k × k)이다.
 
스타트는 자신의 구호 ‘BOJ’를 외치면서 링크를 만나러 가려고 한다. 따라서 스타트가 밟는 보도블럭은 차례로 B, O, J, B, O, J, ...가 적혀있어야 한다.
 
즉 B가 적힌 블록을 밟았으면 다음 번에는 O가 적힌 블록으로, O가 적힌 블록을 밟았으면 다음 번에는 J가 적힌 블록으로,
 
J가 적힌 블록을 밟았으면 다음 번에는 B가 적힌 블록으로 점프해야한다. 단 스타트가 링크를 만나기 위해 1번 보도블럭에서 N번 보도블럭까지점프하여 이동할 때 필요한
 
에너지 양의 최소값을 구하는 프로그램을 작성하시오. 단, N번 블록에 적힌 알파벳이 꼭 ‘J’일 필요는 없다.

Input

첫째 줄에 N(1 ≤ N ≤ 1,000)이 주어진다.
 
둘째 줄에는 보도블럭에 써 있는 알파벳 대문자가 1번부터 순서대로 주어진다.

Output

스타트가 링크를 만나는데 필요한 에너지 양의 최소값을 출력한다. 만약, 스타트가 링크를 만날
 
수 없는 경우에는 -1을 출력한다.

Sample Input

Sample Output

8
BJJOOOBB
-1

Source

shake! 2016 예선