만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

카드 게임

면접 대비

시간 제한1초메모리 제한1024 MB

요약
카드 한 장을 다른 위치로 옮기는 동작으로 같은 무늬를 묶고 각 무늬를 번호 순으로 정렬하며, 하늘색(C) 카드를 맨 뒤에 두는 최소 동작 수를 구합니다.
난이도

보통10점 중 5점

유형
동적 계획법, 이분 탐색, 배열
정답자
아직 제출이 없습니다

문제

파리 올림픽이 곧 열립니다. 당신은 친구 네 명과 함께 스포츠 클라이밍 입장권 다섯 장을 구했습니다. 입장권은 두 시간도 안 되어 모두 매진되었습니다. 경기 시작을 기다리는 동안 좋아하는 카드 게임을 하기로 합니다.

카드 덱에는 색이 서로 다른 표준 무늬 네 가지가 있습니다. 은색 S, 흰색 W, 에메랄드색 E, 빨간색 R입니다. 여기에 으뜸 무늬인 청록색 C가 하나 더 있습니다. 청록색 카드는 다른 모든 카드보다 높습니다. 각 무늬에는 1부터 NN까지 번호가 붙은 카드가 NN장씩 있으므로, 덱은 모두 5N5N장입니다. 게임을 시작하면 덱을 무작위로 다섯 명에게 나누어 주며, 각자 NN장씩 받습니다.

게임을 하기 전에 손패를 정리하려고 합니다. 같은 무늬의 카드는 서로 붙어 있어야 하고 번호는 오름차순이어야 합니다. 청록색 카드는 맨 뒤에 오며 역시 오름차순입니다. 카드는 한 줄로 손에 들어옵니다. 한 번의 동작에서 카드 한 장을 손에서 빼내어 다른 위치에 다시 넣을 수 있습니다. 위치는 두 카드 사이, 맨 앞, 맨 뒤 중 하나입니다.

손패를 정리하는 데 필요한 최소 동작 횟수를 구하세요.

입력

첫째 줄에 NN이 주어집니다. 둘째 줄에는 공백으로 구분된 NN개의 값이 주어집니다. 각 값은 무늬를 나타내는 문자 {S, W, E, R, C} 중 하나와, 카드 번호를 나타내는 정수 VV(1≤V≤N1 \le V \le N)로 이루어져 있습니다.

출력

최소 동작 횟수를 한 줄에 출력합니다.

제한

1≤N≤100 0001 \le N \le 100\,000

예제2

  1. 예제 1

    입력
    4
    C1 R2 E4 R1
    
    예상 출력
    2
    
  2. 예제 2

    입력
    5
    S2 W4 E1 R5 C1
    
    예상 출력
    0