题目描述

田忌和齐王各有 $n$ 匹马，田忌的马速度分别为 $a1,a2,\dots,a_n$，而齐王的马速度分别为 $b1,b2,\dots,b_n$。

田忌与齐王比赛 $n$ 轮，双方每轮挑出一匹新马，若田忌的马更快，田忌加一分，若齐王的马更快，齐王加一分，若双方速度一样，分数不变。

齐王永远按照固定的顺序选择马匹参赛，田忌应该采取什么策略才能让自己的得分减齐王的得分变得最大？

输入格式

第一行：单个整数 $n$ 第二行：$n$ 个整数 $a1,a2,\dots,a_n$ 第三行：$n$ 个整数 $b1,b2,\dots,b_n$

输出格式

单个整数：表示田忌得分减齐王得分的最大值

3
10 20 30
15 25 35

1

数据范围

• 对于 $30\%$ 的数据，$n\leq 20$
• 对于 $60\%$ 的数据，$n\leq 2000$
• 对于 $100\%$ 的数据，$n\leq 200,000$
• $1\leq a_i,b_i\leq 1,000,000$