问题描述

JOI 君有三种类型的印章：圆形印章、叉形印章和圆叉组合印章。他至少有 $0$ 个以上的每种印章。这些印章可以在纸上印出圆圈或叉形标记。

使用圆形印章可以印出一个圆圈，使用叉形印章可以印出一个叉形。使用圆叉组合印章可以在一行中分别印出一个圆圈和一个叉形。通过改变印章的方向，可以将圆圈印在右边，将叉形印在圆圈右边。

JOI 君使用他拥有的印章，按照任意顺序使用每种印章恰好一次，在纸上印出一行圆圈和叉形。印出的圆圈和叉形的序列用字符串 $S$ 表示。$S$ 是一个由 O 和 X 构成的长度为 $N$ 的字符串，其中 $S_i =$ O 表示 JOI 君印出的标记中从左到右数第 $i$ 个标记是圆圈，$S_i =$ X 表示它是一个叉形 ($1 ≦ i ≦ N$)。

你知道 JOI 君拥有的印章数量，但不知道具体数量。从印出的圆圈和叉形序列中，找出可能的圆叉组合印章数量的最大值。

约束条件

• $1 ≦ N ≦ 100000 (= 10^5)$
• $S$ 是长度为 $N$ 的字符串。
• $S$ 的每个字符是 O 或 X。

输入

输入以以下形式从标准输入给出。

$N$ $S$

输出

输出 JOI 君拥有的可能的圆叉组合印章数量的最大值。

输入示例1

5
OXXOX

输出示例1

2

JOI 君印出的标记顺序是：圆圈、叉形、叉形、圆圈、叉形。假设 JOI 君分别拥有 $0$ 个圆形印章、$1$ 个叉形印章和 $2$ 个圆叉组合印章，则可以按以下顺序使用印章来实现该标记的印制：

• 使用第一个圆叉组合印章，按照该顺序印出圆圈和叉形。
• 紧接着，在其右边使用第二个圆叉组合印章，按照该顺序印出叉形和圆圈。
• 最后，在其右边使用叉形印章，印出叉形。

因为不能拥有 $3$ 个或更多的圆叉组合印章，所以输出为 $2$。

输入示例2

14
OXOXOXOXXOXOXO

输出示例2

7

输入示例3

10
OOOOOOOOOO

输出示例3

0