Why Did the Cow Cross the Road II (Gold)#10539
Farmer John raises breeds of cows, conveniently numbered from to . Some pairs of breeds are friendlier than others, a property that can be characterized simply in terms of their breed IDs: breeds and are friendly if |a - b| \leq 4, and unfriendly otherwise.
A long road runs through FJ's farm. There is a sequence of fields on one side of the road, with one field designated for each breed, and another sequence of fields on the opposite side, also with one field for each breed. To help his cows cross the road safely, FJ wants to build crosswalks connecting fields on opposite sides of the road. A crosswalk may connect two fields only if their breed IDs are friendly.
Given the order of the fields on each side of the road, help FJ determine the maximum number of crosswalks he can build such that no two crosswalks intersect.
The first line contains number n~(1 \le n \le 1000).
The next lines describe the order of the fields on one side of the road by their breed IDs. Each breed ID is an integer from to .
The following lines describe the order of the fields on the other side of the road, again by breed ID. Each breed ID appears exactly once in each ordering.
Print the maximum number of non-intersecting "friendly crosswalks" Farmer John can build across the road.
Example 1