Malnar's Palindromic Query Interactive

This is an interactive problem. In this problem, the interactive library is non-adaptive.

Magician Malnar needs to determine the length \(L\) of the longest palindromic substring of a volunteer's imagined word. The word consists of \(N\) lowercase letters. You can determine \(L\) by performing the following interaction:

1. Query: Output ? l r to ask whether the substring in the interval \([l, r]\) is a palindrome. The program will return 1 if it is a palindrome or 0 otherwise. You are allowed at most 200000 queries.
2. Answer: Once you have determined \(L\), output ! L and terminate the program.

Interaction Rules:

• Flush the output immediately after every output (for example, in Python, use flush=True).
• The input provides an integer \(N\) representing the length of the word, and every query interval \([l, r]\) must satisfy \(1 \leq l \leq r \leq N\).

Note: For the purpose of testing, the interaction will be simulated by directly providing the secret word as input. Your solution should read the input and compute the length of the longest palindromic substring without performing any queries.

inputFormat

The input consists of two lines:

• The first line contains an integer \(N\), the length of the word.
• The second line contains a string \(S\) of \(N\) lowercase letters.

outputFormat

Output a single line containing an integer \(L\), the length of the longest palindromic substring in \(S\).

sample

3
aaa

3