Problem Description

Ksenia is learning the English alphabet. She considers a string to be alphabetical if and only if all its letters are consecutive in the alphabet.

For example, the strings abc, xy, fg are alphabetical, while adef, zxc, zab are not.

Ksenia has a ring with letters written on it. She wants to find the longest alphabetical string on this ring and output its length.

A string belongs to the ring if and only if all its characters are adjacent on the ring. In the ring, adjacent characters are the characters numbered $1$ and $2$, $2$ and $3$, $\ldots$, $n-1$ and $n$, and $n$ and $1$. For example, the string abc belongs to the ring bcda, while the string bda does not.

Input Format

The first line contains an integer $n$ ($1 \leq n \leq 10^4$) — the length of the ring.

The second line contains a lowercase Latin string of length $n$ — the letter ring.

Output Format

Output one number — the length of the longest alphabetical string that belongs to the ring.

4
bcda

4

5
edcba

1

8
bcmnopza

4

Hint

Sample Explanation

Explanation for the first test case:

The string abcd satisfies the condition (indices 4, 1, 2, 3 are adjacent), and it is the longest.

Explanation for the second test case:

Among all alphabetical strings with only one letter, the string a is the smallest.

Explanation for the third test case:

Among all alphabetical strings, the string mnop is the longest.

The full English alphabet in order is:

abcdefghijklmnopqrstuvwxyz.

Scoring

If the longest alphabetical string belongs exactly to the input string (rather than the ring), then a solution that correctly handles this case will receive $60$ points.

Translated by DeepSeek V3.

Translated by ChatGPT 5