409236: GYM103464 C Protected String

Alexandrik — a well-known security software developer. Today he thought he'd been hacked, so he decided to update the passwords on all his accounts.

To do that, Alexandrik invented a special hard-to-crack string $$$s$$$, which for some reason consists only of the letters a' and b'. And now he wants to choose the largest «perfectly protected» substring from it, for only it will ensure the safety of his precious personal data. Recall that a substring is a contiguous subsegment of a string. For example, for string ababaaa, string bab is a substring because it lies in that string continuously (ababaaa). At the same time, the string abb is not a substring, because although it enters this string (ababaaa), it does not lie in this string continuously. The string bbb is also not a substring, because it does not lie in this string at all.

A string is called «perfectly protected» if it turns out that every character of this string is different from the corresponding character in its «inverted» version (i.e. a string in which the characters of the original string are written in reverse order). So, for example, the string abaabbab is «perfectly protected» because:

abaabbab

babbaabaaba

are distinct in each character. At the same time, the string aaabaabb is not «perfectly protected», because its «inverted» version (babaabaaa) matches the original string in the third and sixth positions.

So, help Alexandrik find the longest substring of his string, which is «perfectly protected».

The first line of input contains a single integer $$$n$$$ —the number of characters in the string $$$s$$$ ($$$2 \le n \le 5 \cdot 10^5$$$).

The second line of input data contains the string $$$s$$$ itself, consisting of the letters a' and b'.

Print a single non-negative integer — the size of the longest substring of string $$$s$$$, which is «perfectly protected».

In this problem there is a subtask scores. Score for a subtask are counted only if all tests for that subtask are passed. The subtasks are listed in the following table:

9
abbababba

4

12
aaabbaabbaaa

8

10
aabbbabbaa

4

10
aabbbaaabb

10

7
aaaaaaa

0

In the first test case, for example, baba can be selected as a substring.

In the second test case, for example, bbaabbaa can be selected as a substring.

In the third test case, for example, bbaa can be selected as a substring.