田忌赛马

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

齐使者如梁,孙膑以刑徒阴见,说齐使。齐使以为奇,窃载与之齐。齐将田忌善而客待之。忌数与齐诸公子驰逐重射。孙子见其马足不甚相远,马有上、中、下辈。于是孙子谓田忌曰:“君弟重射,臣能令君胜。”田忌信然之,与王及诸公子逐射千金。及临质,孙子曰:“今以君之下驷与彼上驷,取君上驷与彼中驷,取君中驷与彼下驷。”既驰三辈毕,而田忌一不胜而再胜,卒得王千金。于是忌进孙子于威王。威王问兵法,遂以为师。

 

齐国公子输给田忌后,特别不服气,想要再和田忌再比一场,并且这次派出了N匹马。但是这次孙斌不在了,田忌想要请你帮助他安排马的出场顺序,战胜齐国公子。你能帮助田忌获胜吗?

Input

第一行输入一个整数N(1<=n<=3000),代表这次比赛双方各派出n匹马参加比赛。

第二行输入N个整数Ai(1<=i<=N,1<=Ai<=50000),代表公子编号为i的马的速度,数据保证编号越小的马速度越快。

第三行输入N个整数Bi(1<=i<=N,1<=Ai<=50000),代表田忌编号为i的马的速度,数据保证编号越小的马速度越快。

Output

每组数据输出一个整数,代表田忌最多能获胜的局数。(平局不算获胜)

Sample Input

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

Sample Output

5

Hint

Source

【2017级《程序设计基础(B)II》期末上机考试】玄黄