问题 6299 --赛马比赛

6299: 赛马比赛★★

时间限制: 1 Sec  内存限制: 128 MB
提交: 53  解决: 39
[提交][状态][命题人:]

题目描述

自从同学们都学会田忌赛马的策略后,比赛结果越来越难预测了。

为了简化比赛规则,张博士推出来新的策略。

现在你要和张博士赛马,你们各自有N匹马,要进行N轮比赛,每轮比赛,你们都要派出一匹马决出胜负。

你的马匹速度分别为u1,u2,u3,....,uN, 张博士的马匹速度分别为v1,v2,....,vN。

现在你有两种选择,第一种选择是将自己的马匹按速度从慢到快排列,然后依次出战。

第二种选择是将自己的马匹按速度从快到慢排列,然后依次出战。

张博士根据你的选择方案,会选另外一个方案依次派他的马出战。

比如你选择了按马匹速度从快到慢依次派出,那张博士会选择按马匹速度从慢到快出战;

比如你选择了按马匹速度从慢到快依次派出,那张博士会选择按马匹速度从快到慢出战;

请问在你拥有优先选择方案的情况下,你最多能赢几轮。

测试数据保证,你和张博士的所有马匹速度两两不同,因此不可能出现平局。

输入

第一行一个整数N. 保证1<=N<=50000

接下来一行N个用空格隔开的整数,依次为u1,u2,...,uN,表示你的马匹的速度,保证1<=ui<=2N

接下来一行N个用空格隔开的整数,依次为v1,v2,...,vN,表示张博士的马匹的速度,保证1<=vi<=2N

输出

输出一行,表示你最多能获胜几轮
样例输入
Copy
3
1 3 5
2 4 6
样例输出
Copy
1

提示

样例2输入
5
10 3 5 8 7
4 6 1 2 9
样例2输出
3

来源

[提交][状态]