34928번 - PAUL 문자열 (Hard)

문제

이 문제는 Easy 버전과 굵게 표시된 제약 조건을 제외하면 동일합니다.

PAUL 문자열은 P,A,U,L을 각각 하나 이상 포함하는 알파벳 대문자로 이루어진 문자열이다. 모그는 길이 $N$의 PAUL 문자열을 선물받았다. 선물받은 문자열을 가지고 놀던 모그는 "이 문자열의 이웃한 두 문자를 삭제한 뒤 남은 부분을 이어 붙이는 연산을 반복해 정확히 PAUL만 남길 수 있을까?" 하는 궁금증이 생겼다.

머리가 좋지 않은 모그 대신 궁금증을 해결해 주자.

입력

첫째 줄에 모그가 선물받은 PAUL 문자열의 길이 $N$이 주어진다. $(4\le N\le 100,000円)$

둘째 줄에 모그가 선물받은 길이 $N$의 PAUL 문자열이 주어진다. 이 문자열에서 P,A,U,L은 각각 한 번 이상 등장한다.

출력

정확히 PAUL만 남길 수 있다면 YES, 그렇지 않다면 NO를 출력한다.

제한

노트