Pen Pineapple Apple Pen

Time limit1sMemory limit32 MB

Summary

Given a string of A, P, and p, find the maximum number of disjoint subsequence occurrences of the pattern p, P, A, p in order.

Level: Medium5 of 10
Topics: Greedy, String, Dynamic programming
Solved: No attempts yet

Problem

Apples, pineapples, and pens are lined up in a row. You may group four consecutive objects without changing their order. Four objects count as one group only when they appear in the order pen, pineapple, apple, pen. One pen can belong to at most one group. The order pen, apple, pineapple, pen does not count as a group.

Input

The first line gives the total number of objects $n$ ( $1 \le n \le 1000000$ ).

The second line gives the list of objects as a string of length $n$ . An apple is written as A, a pineapple as P, and a pen as p, distinguishing uppercase and lowercase.

Output

Print the maximum number of groups that can be made.

Examples2

Example 1
Input
```
15
ApPApPpAPpApPAp
```
Expected output
```
2
```
Example 2
Input
```
7
pPApPAp
```
Expected output
```
1
```