JOIOJI is JOI's uncle. JOIOJI likes his name, which contains two each of the characters J, O, and I.
Recently, a child was born to JOIOJI. JOIOJI is thinking of giving his child a name that, like his own, consists of J, O, and I, with exactly the same number of each character.
JOIOJI possesses a scroll passed down through his family. A poem is written on the scroll. The poem is a string of length $N$ consisting only of the three characters J, O, and I. JOIOJI intends to name his child after the longest contiguous substring in the poem that contains exactly the same number of J, O, and I characters.
Task
Given the information about the poem written on JOIOJI's scroll, write a program to find the maximum length of a contiguous substring in the poem that contains exactly the same number of J, O, and I characters.
Input
Read the following data from standard input:
- The first line contains an integer $N$, representing the length of the poem on JOIOJI's scroll.
- The second line contains a string $S$ of length $N$, representing the poem on JOIOJI's scroll. Each character of $S$ is one of J, O, or I.
Output
Output a single integer representing the maximum length of a contiguous substring in the poem that contains exactly the same number of J, O, and I characters. If no such substring exists, output 0.
Constraints
All input data satisfies the following condition:
- $1 \le N \le 200\,000$
Subtasks
Subtask 1 [5 points]
- $N \le 200$
Subtask 2 [15 points]
- $N \le 4\,000$
Subtask 3 [80 points]
- No additional constraints.
Examples
Input 1
10 JOIIJOJOOI
Output 1
6
Note 1
In this example, the scroll contains a poem of length 10, JOIIJOJOOI. This poem contains the contiguous substring IIJOJO, which has exactly 2 each of J, O, and I. Since there is no contiguous substring containing 3 or more of each of J, O, and I, we output the length of IIJOJO, which is 6.
Input 2
8 IOIIJIIO
Output 2
0
Note 2
Since the poem does not contain any substring that satisfies the condition, we output 0.
Input 3
20 JJIOOIJIJOIOJIOJOOIJ
Output 3
15