Longest Transposable Theme

We represent a piece of music as a sequence of \(N\) notes (\(1 \leq N \leq 5000\)). Each note is an integer between \(1\) and \(88\), corresponding to a key on the piano. Many composers structure their music around a recurring theme. In our representation, a theme is defined as a contiguous subsequence of the notes that satisfies the following conditions:

1. The theme has at least \(5\) notes.
2. The theme appears at least twice in the entire sequence (the occurrences may be transposed).
3. The occurrences of the theme do not overlap.

A transposition means that every note in the theme is shifted by the same integer value. In other words, two subsequences \(A = (a_1, a_2, \ldots, a_L)\) and \(B = (b_1, b_2, \ldots, b_L)\) are considered the same theme (up to transposition) if there exists an integer \(C\) such that \(b_i = a_i + C\) for all \(i = 1, 2, \ldots, L\). Equivalently, the pattern of differences \( (a_2-a_1, a_3-a_2, \ldots, a_L-a_{L-1}) \) is the same for both occurrences.

Your task is to determine the length (in number of notes) of the longest theme within a given musical piece. If no valid theme exists, output \(0\).

inputFormat

The input consists of two lines:

The first line contains an integer \(N\), the number of notes in the sequence.

The second line contains \(N\) space-separated integers, each between \(1\) and \(88\), representing the notes.

outputFormat

Output a single integer representing the length of the longest theme. If no theme exists, output \(0\).

sample

10
1 2 3 4 5 6 7 8 9 10

0