A. But First, Coffee
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Lois Griffin has hung a new sign in the kitchen: "But first, coffee." Peter finds this deeply illogical, as you can't say something comes "first" without knowing what it's being compared against.

To settle the argument, Peter gathers a line of $$$n$$$ people in the kitchen, represented as a string $$$s$$$. Each person either wants coffee $$$(s_i = \texttt{C})$$$ or is having a life-threatening emergency $$$(s_i = \texttt{E})$$$.

Lois insists that coffee should always come first, so she wants to rearrange the line so that all $$$\texttt{C}$$$'s appear before all $$$\texttt{E}$$$'s. Lois can only perform the following operation, any number of times:

— Choose 3 indices $$$1 \leq i \lt j \lt k \leq n$$$ and right shift or left shift the values on $$$s_i$$$, $$$s_j$$$, $$$s_k$$$ cyclically.

For the string $$$\texttt{CCECCE}$$$, if she chooses $$$i=1, j=2, k=3$$$ and performs a right shift cyclically, the string becomes $$$\texttt{ECCCCE}$$$. If she chooses $$$i=4, j=5, k=6$$$ and performs a left shift cyclically instead, the string becomes $$$\texttt{CCECEC}$$$.

Determine the minimum number of operations Lois needs to rearrange $$$s$$$ so that all people who want coffee come before all people having emergencies.

Input

The first line contains $$$n$$$ $$$(3 \leq n \leq 10^5)$$$ — the length of the string.

The second line contains $$$s$$$, of length $$$n$$$. A character in $$$s$$$ will only be either $$$\texttt{C}$$$ or $$$\texttt{E}$$$.

Output

Output a single integer — the minimum number of operations required to sort the given string $$$s$$$.

Examples
Input
3
CCE
Output
0
Input
4
CEEC
Output
1
Input
6
EECECC
Output
2
Input
6
ECECEE
Output
1
Note

In the first sample, CCE is already in the required order, so the answer is $$$0$$$. In the second sample, one cyclic shift using positions $$$1$$$, $$$2$$$, and $$$4$$$ changes CEEC into CCEE, so one operation is enough.