Алгоритмы и структуры данных

Максимальная длина общего подмассива

Даны два целочисленных массива a и b. Требуется найти максимальную длину подмассива, который встречается и в a, и в b.

Входные данные

В первой строке входных данных содержится одно целое число n (1 ≤ n ≤ 1000).

Во второй строке записаны n целых чисел, разделённых пробелами: (0 ≤ ≤ 100).

В третьей строке записаны n целых чисел, разделённых пробелами: (0 ≤ ≤ 100).

Выходные данные

Программа должна вывести максимальную длину общего подмассива.

Примеры

Input

Output

4
1 2 4 2
0 4 2 1

2

3
5 5 5
5 5 5

3

Пояснение

  1. Самый длинный общий подмассив — 4 2, который содержится в обоих массивах ⇒ длина 2

  2. Оба массива совпадают ⇒ самый длинный общий подмассив — это сам данный массив ⇒ длина 3

Constraints

Time limit: 2 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue