Sensor Calibration Single Swap

A field technician logs two aligned lists of sensor readings for n sensors, indexed 0 to n-1: raw[i] is a sensor's uncorrected reading, and target[i] is the reading it should have after a full recalibration. The current mismatch score is the sum, over all sensors, of |raw[i] - target[i]|. Before filing the report, the technician may perform at most one quick fix: pick a single index i and overwrite raw[i] with the value taken from raw[j] for some other index j (any value already present at another position in the original raw list may be reused this way, but at most one position may be changed, and the replacement value must come from the original list, not be invented). Determine the smallest mismatch score achievable — whether by making one such substitution or by making none at all — and print it modulo 1,000,000,007.

Input Format

• Line 1: a single integer n, the number of sensors.
• Line 2: n space-separated integers raw[0], ..., raw[n-1].
• Line 3: n space-separated integers target[0], ..., target[n-1].

Output Format

Print a single integer: the minimum achievable mismatch score, taken modulo 1,000,000,007.

Constraints

• 1 <= n <= 100000
• 1 <= raw[i] <= 100000
• 1 <= target[i] <= 100000

4
2 4 6 8
3 8 6 1

6

3
10 20 30
25 25 25

15