Description

We represent a piece of music by a sequence of $N$ ($1 \le N \le 5000$) notes, each an integer in the range $1 \sim 88$, where each number denotes a key on the piano. Unfortunately, this way of encoding a melody ignores note durations, but this programming task concerns pitch only and is independent of duration.

Many composers build a piece around a recurring "theme". In our representation, a "theme" is a substring of the entire note sequence that satisfies the following conditions:

1. Its length is at least $5$ notes.
2. It appears repeatedly in the piece (possibly after transposition, see below).
3. The repeated occurrences of the same theme must be non-overlapping.

"Transposition" means that each note in the theme sequence is increased or decreased by the same integer. Given a piece, compute the length (number of notes) of the longest theme.

The time limit for this problem is $1$ second.

Input Format

The first line of input contains the integer $N$.

Each of the following lines (except possibly the last) contains $20$ integers representing the note sequence.

The last line may contain fewer than $20$ notes.

Output Format

Output a single integer, the length of the longest theme. If there is no theme, output 0.

30
25 27 30 34 39 45 52 60 69 79 69 60 52 45 39 34 30 26 22 18
82 78 74 70 66 67 64 60 65 80

5

Hint

The statement is translated from NOCOW.

USACO Training Section 5.1.

Translated by ChatGPT 5