[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$ 个牧场的奶牛品种编号。
输出格式
输出最多能画多少条人行道。
输入输出样例
输入样例 #1
6
1
2
3
4
5
6
6
5
4
3
2
1
输出样例 #1
5