题目描述

有一个字符串，只含有 N、O、I 三种字符。小 M 打算通过插入一个字符的方式，使其“AK 方案数”最大。

所谓“AK 方案”，就是指的在字符串里面删掉几个字符，使字符串变成 NOI。两种方案不同当且仅当在原字符串中有一个字符，在第一种方案中被删去了，第二种方案中没被删去。

输入格式

第一行一个正整数 $n$ 表示字符串的长度。

接下来一行一个长度为 $n$ 的字符串。

输出格式

输出一个正整数，代表插入一个字符（可以插在字符串开头、结尾或两个字符之间）后，可以达到的最大“AK 方案数”。

3
IOI

1

8
NONONONO

10

3
NOI

2

提示

样例解释 1

把一个字符 N 插到字符串开头（插到第一个字符和第二个字符之间也行），这样“AK 方案数”是 $1$。

样例解释 2

把一个字符 I 插到字符串结尾。

数据范围

对于 $30\%$ 的数据，$n \le 200$。

对于 $50\%$ 的数据，$n \le 2\times10^3$。

对于 $100\%$ 的数据，$1\le n\le{10}^5$。