测试数据来自 system/3065

该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

时间限制：1秒　　内存限制：256M

---

【问题描述】

　　设 \(t_1,t_2,…,t_k\) 是序列 \(A\) 和 \(B\) 的公共子序列，且满足下列关系：

　　　　\(t_1 > … > t_i < t_{i+1} < … < t_k（1≤i≤k）\)

　　我们称 \(t_1,t_2,…,t_k\) 是序列 \(A\) 和 \(B\) 的凹形公共子序列。

　　现在给出两个长度均为 \(n\) 的整数序列 \(A\) 和 \(B\)，请编程求它们的最长的凹形公共子序列的长度。

【输入格式】

　　第一行是一个整数 \(n\)，表示序列的长度。接下来的两行每行有 \(n\) 个整数，分别表示序列 \(A\) 和 \(B\)。同行相邻整数间用一个空格分开。

【输出格式】

　　输出一个整数，表示答案。

【输入输出样例】

　Input

11
1 4 5 3 1 6 2 7 4 2 9
7 5 4 6 3 1 6 8 7 9 3

　Output

6

【数据限制】

　　50%的数据满足：\(1≤n≤500\)
　　100%的数据满足：\(1≤n≤5000\)，序列的整数都是C++的int。

【来源】

　　Mr.he