The Longest Bar Magnet

Interview

Time limit1sMemory limit1024 MB

Summary

Find the length of the longest substring that is a block of one letter followed by an equal-length block of the other letter, for a string of N and S.

Level: Easy3 of 10
Topics: String, Implementation
Solved: No attempts yet

Problem

A magnet string is a string made only of the characters N and S that satisfies the following conditions. The number of N characters in the string equals the number of S characters, and the characters in the first half of the string are all N or all S. For example, NS, NNSS, and SSSNNN are magnet strings, but SNS, NNNSS, and NSNS are not.

Yoon has a string made of N and S. Yoon wants to find the longest magnet string among the substrings of this string. A substring is a contiguous part of a string. Find the length of the longest magnet string that Yoon can find among the substrings of the given string.

Input

The first line contains the length $K$ of the string ( $1\leq K\leq 300\ 000$ ).

The second line contains a string of length $K$ made only of the characters N and S.

Output

Print the length of the longest magnet string among the substrings of the given string. If no magnet string can be found, print $0$ instead.

Examples2

Example 1
Input
```
8
NSSSNNSN
```
Expected output
```
4
```
Example 2
Input
```
5
NNNNN
```
Expected output
```
0
```