Longest Typographic River

In typesetting, a river is a string of spaces formed by gaps between words that extends down several lines of text. In left‐aligned, mono-spaced columns with exactly one space between words, a river is defined as a sequence of space characters in consecutive lines. The sequence may wander by at most one column per line: that is, if a space appears in column c in one line, the space continuing the river in the next line must appear in column c-1, c, or c+1 (except the first space in the chain). Note that trailing white space is not allowed to be part of a river.

Given a text consisting of several words, you are to choose a line width such that when the text is typeset as follows:

• Words are printed in order.
• No word is split.
• Words are separated by exactly one space.
• Each line is filled as tightly as possible (i.e. a word that fits is printed on the current line; otherwise it goes to the next line).
• The line width is at least as long as the longest word.
• There is no extra trailing space at the end of a line.

you must determine the line width (an integer) in the range from \(L_{\min}=\max\{\text{length of a word}\}\) to \(L_{\max}=\) (total length of the text with single spaces) that produces the longest river of spaces. In the typeset text for a given width, consider each gap (i.e. space between consecutive words on a line) at its column position (its 1-indexed position in the line). A river is any chain of such spaces on consecutive lines where for each space (except the first in the chain) the column differs by at most \(1\) compared to the space immediately above it. If there are multiple widths that yield a longest river (i.e. maximum number of consecutive lines connected), choose the smallest width among them.

Note: If the text is printed in a single line (or there are no gaps in some line), then the longest river length is taken as 1 (or 0 if no gap is present at all). In such a case, output the corresponding width.

inputFormat

The input consists of two lines.

• The first line contains an integer \(n\) (\(1 \le n \le 1000\)), representing the number of words.
• The second line contains \(n\) words separated by single spaces. Each word is a non-empty string of uppercase letters.

outputFormat

Output a single integer: the line width (between \(L_{\min}\) and \(L_{\max}\)) that produces the longest river of spaces when the text is typeset as described. In case of ties, output the smallest such width.

sample

5
THIS IS A SAMPLE TEXT

14