Longest shared run: hints, no solution

Two versions of a document are stored as lists of paragraph ids, a and b. A shared run is a block of consecutive paragraphs that appears in both versions, in the same order and with no gaps. Return the length of the longest shared run, or 0 if the versions have no paragraph in common. Ids can repeat within a version, and either version may be empty.

Examples

Input

a = [7, 1, 2, 3, 9], b = [5, 1, 2, 3, 4, 9]

Output

3

Note

The block 1, 2, 3 appears in both. The 9 is shared but separated from it.

Input

a = [4, 4], b = [5, 6]

Output

0

Note

No paragraph appears in both versions.

Input

a = [1, 2, 1, 2, 1], b = [2, 1, 2, 1, 2, 1]

Output

5

Constraints

• 0 <= a.length, b.length <= 2500
• 1 <= a[i], b[i] <= 1000000

Hint 1: a nudge

Suppose a paragraph in a matches a paragraph in b. What would you want to know about the paragraphs just before each of them to tell how long the run is?

Unlock the full hints and timed practice with a pass

The second and third hints and the timed, runner-checked practice are part of a pass.

See pricing