Problem Description

You are given a string $ S $ of length $ N $ consisting of the characters U, T, P, C.

You can perform the following operation any number of times:

• Choose integers $i,\ j\ \,\ (1\ \leq\ i\ <\ j\ \leq\ N)$. Swap the $ i $-th and $ j $-th characters of $ S $.

Find the minimum number of operations needed to make the string $ S $ satisfy the following condition:

• $ S $ contains the substring UTPC as a contiguous subsequence.

It is guaranteed that $ S $ contains at least one of each character U, T, P, C.

Input Format

The input is given from the standard input in the following format:

$ N $ $ S $

Output Format

Output the minimum number of operations needed to make the string $ S $ satisfy the condition.

Sample Input and Output

Sample Input #1

5
UTCUP

Sample Output #1

2

Sample Input #2

4
UTPC

Sample Output #2

0

Sample Input #3

20
PTPUTPTUCPTUPTUPCTPC

Sample Output #3

1

Notes/Hints

Constraints

• $4\ \leq\ N\ \leq\ 10000$
• $ S $ is a string of length $ N $ consisting of U, T, P, C
• $ S $ contains at least one of each character U, T, P, C

Sample Explanation 1

By performing 2 operations like UTCUP $\rightarrow$ UTPUC $\rightarrow$ UTPCU, the substring from the 1st to the 4th character becomes UTPC, satisfying the condition of $ S $.

Sample Explanation 2

If the condition is already satisfied from the beginning, output $ 0 $.

见题面 Input 部分

见题面 Output 部分