[고등부] 2023 KOI 대비 모의고사 (4월 4주차)

미어캣은 사진에서 보이는 것처럼 두 발로 서서 천적을 경계하며 보초를 선다.

정올 어린이대공원에는 N마리의 미어캣이 일렬로 나란히 서 있다. 편의상 왼쪽부터 순서대로 1번부터 N번까지 번호를 붙이자.

이 미어캣들은 왼쪽 또는 오른쪽 중 한 방향을 바라보고 서 있다. 잘 알려지지 않은 사실이지만, 미어캣은 자신이 바라보는 방향에 자신과 키가 같거나 더 큰 미어캣이 있으면 기분이 나빠진다.

작고 귀여운 외모와 달리, 비록 몸집은 작지만 독사도 사냥하는 몽구스과 특유의 강력한 전투력을 지녔기에 기분이 나빠지면 매우 위험하다. 사육사는 이 사실을 알고 모든 미어캣이 불쾌해하지 않도록 일부를 야생으로 방생하려 한다.

그러나 방생 작업은 쉽지 않으므로, 방생할 미어캣 수를 최소화하고 싶다. 모든 미어캣이 기분 나빠하지 않게 만들기 위해 최소 몇 마리의 미어캣을 방생해야 하는지 계산하는 프로그램을 작성하자.

입력

첫 번째 줄에 미어캣의 수 N이 입력된다. (1 ≤ N ≤ 3\cdot 10^5)

두 번째 줄에는 각 미어캣이 바라보고 있는 방향을 나타내는 문자열이 입력된다.

문자열은 왼쪽을 의미하는 L과 오른쪽을 의미하는 R로만 이루어져있으며, i번째 문자는 i번째 미어캣이 바라보는 방향이다.

세 번째 줄에는 1번부터 N번까지의 미어캣의 키 H_i가 공백을 기준으로 순서대로 입력된다. (1 ≤ H_i ≤ 10^9, H_i는 정수)

출력

첫 줄에 모든 미어캣들을 기분 나쁘지 않게 하기 위한 최소 방생 횟수를 출력하시오.

부분문제

미어캣
서브태스크

1초 32MB