JJOOII

Interview

Time limit1sMemory limit128 MB

Summary

Find the largest k such that k J's, then k O's, then k I's appear consecutively in the given string.

Level: Medium5 of 10
Topics: String, Prefix sum, Binary search
Solved: No attempts yet

Problem

We work with strings made up of only the three characters J, O, and I.

A string $t$ is a substring of a string $s$ if $s$ can be formed by adding zero or more characters to both the front and the back of $t$ ; that is, $t$ must appear contiguously inside $s$ . For example, JJOOII is a substring of OJJOOIIOJOI, whereas JOI is not a substring of JOOI.

For a non-negative integer $k$ , a level- $k$ JOI sequence is the string consisting of $k$ copies of J, then $k$ copies of O, then $k$ copies of I, in that order. For example, JJOOII is a level- $2$ JOI sequence.

You are given a string $S$ of length $N$ over the characters J, O, and I. Find the largest $k$ such that a level- $k$ JOI sequence is a substring of $S$ .

Input

The first line contains the string $S$ , made up of the characters J, O, and I.

Output

Print, on a single line, the largest $k$ such that a level- $k$ JOI sequence is a substring of $S$ . (If no level- $1$ -or-higher JOI sequence is a substring, print 0.)

Constraints

$1 \le N \le 1\,000\,000$ , where $N$ is the length of $S$ .

Examples4

Example 1
Input
```
OJJOOIIOJOI
```
Expected output
```
2
```
Example 2
Input
```
IJJIIJJJ
```
Expected output
```
0
```
Example 3
Input
```
JOIJOIJOIJOIJOI
```
Expected output
```
1
```
Example 4
Input
```
OOJJJJJJJOOOOIIIII
```
Expected output
```
4
```