Pen Pineapple Apple Pen

A, P, p로 이루어진 문자열에서 p, P, A, p 순서를 이루는 서로 겹치지 않는 부분 수열의 최대 개수를 구한다.

보통5그리디문자열동적 계획법아직 제출이 없습니다시간 제한1초메모리 제한32 MB

문제 설명

예제2

문제

사과, 파인애플, 펜이 일렬로 놓여 있다. 순서를 바꾸지 않고 연속된 네 개의 물건을 묶을 수 있다. 네 개의 물건이 펜, 파인애플, 사과, 펜 순서일 때만 하나의 묶음으로 인정한다. 하나의 펜은 최대 하나의 묶음에만 속할 수 있다. 펜, 사과, 파인애플, 펜 순서는 묶음으로 인정하지 않는다.

입력

첫째 줄에 물건의 총 개수 $n$ 이 주어진다 ( $1 \le n \le 1000000$ ).

둘째 줄에 물건의 목록이 길이 $n$ 의 문자열로 주어진다. 사과는 A로, 파인애플은 P로, 펜은 p로 표기하며 대소문자를 구분한다.

출력

만들 수 있는 묶음의 최대 개수를 출력한다.