← 返回题目列表

AtCoder · yahoo_procon2017_qual_e

E. 游园地

中文机器翻译题面 查看原题

配点 : 1200 点

問題文

高桥君来游乐园玩了。游乐园里有 N 个游乐设施排列成一列,依次 1,\ 2,\ ...,\ N 。

此外,要在这个游乐园玩需要体力,移动相邻的游乐设施会消耗体力。 1 另外,i 第几个游乐设施需要体力 L_i 以上才能玩,玩过之后体力刚好成为 R_i 。 不过,由于某些游乐设施的趣味性,玩过之后体力有时甚至会比原来增加。

高桥君想玩尽可能多种类的游乐设施。请在选择好最初玩的游乐设施以及之后游乐设施的顺序时,求出高桥君最多能玩几种类的游乐设施。 不过,高桥君一开始心情非常好,可以假设体力无限。

制約

  • 1 ≦ N ≦ 50,000
  • 1 ≦ L_i ≦ 10^9
  • 1 ≦ R_i ≦ 10^9

入力

输入是按以下格式从标准输入给出的。

N 
L_1 L_2 ... L_N
R_1 R_2 ... R_N

出力

输出高桥君能够乘坐的游乐设施种类数的最大值。


入力例 1

3
5 1 3
1 2 4

出力例 1

2

第一 3 在第几种游乐设施玩之后 2 如果之后玩第几种游乐设施,高桥君就可以 2 玩这种类的游乐设施。


入力例 2

5
3 1 2 4 5
2 5 4 1 3

出力例 2

3