[USACO17FEB] Why Did the Cow Cross the Road II P

*本题与 [金组同名题目](/problem/P6119) 在题意上一致，唯一的差别是数据范围。*

Farmer John 饲养了 $N$ 种奶牛，编号从 $1$ 到 $N$。一些品种的奶牛和其他奶牛间相处良好，事实证明，如果两个品种的奶牛编号分别为 $a,b$，当 $|a-b| \leq 4$ 时，这两个品种的奶牛能友好相处，否则不能友好相处。 一条长长的道路贯穿整个农场，道路的左侧有 $N$ 个牧场（每个品种的奶牛恰好占据一个牧场），道路的右侧也有 $N$ 个牧场（每个品种的奶牛恰好占据一个牧场）。为了让奶牛们安全穿过马路，Farmer John 希望能在马路上画出一些人行道（牛行道？），要求这些人行道满足如下条件： 1. 人行道从左侧的某个牧场出发，连接到右侧的某个牧场； 2. 人行道连接的两个牧场的奶牛要能友好相处； 3. 人行道不能在道路中间相交； 4. 每个牧场只能与一条人行道相连。 你需要帮 FJ 求出最多能有多少条人行道。

输入第一行一个整数 $N$（$1 \leq N \leq 10^5$）。 接下来 $N$ 行，每行一个整数 $a_i$，代表道路左侧第 $i$ 个牧场的奶牛品种编号。 接下来 $N$ 行，每行一个整数 $b_i$，代表道路右侧第 $i$ 个牧场的奶牛品种编号。

输出最多能画多少条人行道。

6
1
2
3
4
5
6
6
5
4
3
2
1

5