Dãy con chung dài nhất

Cho hai mảng \(A\), \(B\) đều gồm \(n\) phần tử, hãy tìm độ dài dãy con chung dài nhất (LCS) của mảng \(A\) và \(B\).

Nói cách khác, hãy tìm số nguyên \(k\) lớn nhất sao cho tồn tại các chỉ số \(1 \le i_1 < i_2 < \ldots < i_k \le n\) và \(1 \le j_1 < j_2 < \ldots < j_k \le n\) thỏa mãn:

$$
A_{i_1} = B_{j_1},

A_{i_2} = B_{j_2},

\vdots

A_{i_k} = B_{j_k}.
$$

Input

• Dòng đầu tiên chứa số nguyên \(n\) (\(1 \le n \le 1000\)) --- số phần tử trong mỗi mảng.

• Dòng thứ hai chứa \(n\) số nguyên \(A_1, A_2, \ldots, A_n\) (\(1 \le A_i \le 10^9\)).

• Dòng thứ ba chứa \(n\) số nguyên \(B_1, B_2, \ldots, B_n\) (\(1 \le B_i \le 10^9\)).

Output

In ra một số nguyên là độ dài của dãy con chung dài nhất (LCS).

Scoring

• Subtask 1 (30%): \(n \le 20\).

• Subtask 2 (70%): \(n \le 1000\).

Example

Input:

4
1 2 3 4
3 4 2 1

Output:

2

Notes

Một dãy con chung dài nhất là \((3, 4)\).