「みんなのプロコン」

E - 遊園地


Time limit時間制限 : 3sec / Memory limitメモリ制限 : 1024MB

配点 : 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

Submit提出する