You are given two multisets \(A\) and \(B\), each containing \(N\) elements. In one step, you can choose an integer \(x\) from \(A\), delete an occurrence of \(x\) from \(A\), and add either \(x+1\) or \(x - 1\) to \(A\). Determine the minimum number of moves required such that the condition \(A = B\) satisfies.
Input format
- First line: Integer \(N\) \((1 \le N \le 10^5)\)
- Second line: \(N\) integers that represent the multiset \(A\)
- Third line: \(N\) integers that represent the multiset \(B\)
Note: All the numbers are positive integers smaller or equal to \(2^{63} - 1\).
Output format
Print the remainder of the answer when divided by \(10^9 + 7\).
3 4 1 3 2 6 2
4
To obtain the optimal answer we need to perform the following operations:
1. Delete \(1\) and add \(2\), \(A = \{ 2, 3, 4 \}\)
2. Delete \(3\) and add \(2\), \(A = \{ 2, 2, 4 \}\)
3. Delete \(4\) and add \(5\), \(A = \{ 2, 2, 5 \}\)
4. Delete \(5\) and add \(6\), \(A = \{ 2, 2, 6 \}\)
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor
Login to unlock the editorial
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor