Minimum Erosion Cost for Fossil Worm

Scientists have recently discovered fossils of an ancient creature called the “millennium worm”. Its fossilized shape, however, does not exactly match the theoretical model established from nearly complete specimens. The theoretical model describes a worm B by splitting its body into n horizontal strips (rows) of unit squares. In row i, the worm occupies a contiguous block of cells from L[i] to R[i] (inclusive), where all boundaries are parallel to the coordinate axes and of positive integer lengths. Moreover, due to the construction of B, the left and right boundaries (defined by L[i] and R[i] respectively) change gradually: for every two consecutive rows i and i+1, the differences satisfy (|L_i - L_{i+1}| \le 1) and (|R_i - R_{i+1}| \le 1).

A fossil worm A is represented in the same way (with values A.L[i] and A.R[i]), but due to erosion some of the cells originally part of B have been removed. The erosion process occurs one cell at a time and under the following conditions:

1. Erosion happens on whole unit cells only.
2. Erosion is carried out incrementally (one cell per step).
3. A cell will not be eroded if its removal would disconnect the worm.
4. If a cell’s left and right neighbors (in the same row) are both intact, then that cell won’t be eroded at the current step.
5. The cells adjacent to the head and tail (the extreme rows) cannot all be eroded.

Thus, the fossil A is always a subset of some theoretical worm B. In other words, the fossil cells in every row are a (contiguous) subset of B’s cells; that is, for every row i, we have [ L'_i \le A.L_i \quad \text{and} \quad R'_i \ge A.R_i, ] where (n, L'_1, L'_2, \dots, L'_n, R'_1, R'_2, \dots, R'_n) is the description of B. The cost to transform B into A is defined as the number of unit cells that must be eroded, i.e. the difference in area between B and A. Formally, the cost is:

[ \text{cost} = \sum_{i=1}^{n} \Bigl[(R'_i - L'_i + 1) - (A.R_i - A.L_i + 1)\Bigr]. ]

Your task is: Given a fossil worm A (its n rows described by A.L[i] and A.R[i]), choose a theoretical worm B satisfying the following conditions:

• For each row i, B’s interval [L'_i, R'_i] is a superset of A’s interval [A.L_i, A.R_i] (i.e. \(L'_i \le A.L_i\) and \(R'_i \ge A.R_i\)).
• For every two consecutive rows, the boundaries change gradually: \(|L'_i - L'_{i+1}| \le 1\) and \(|R'_i - R'_{i+1}| \le 1\).
• For each row, it holds that \(L'_i \le R'_i\).

Find the worm B that can yield A through a valid erosion process with the minimum possible cost and output that minimum cost.

Note: All coordinates are integers and the cost is measured as the number of cells that need to be eroded.

inputFormat

The first line contains an integer n (the number of rows).

The second line contains n integers: A.L₁, A.L₂, …, A.L_n.

The third line contains n integers: A.R₁, A.R₂, …, A.R_n.

It is guaranteed that for each 1 ≤ i ≤ n, A.L_i ≤ A.R_i.

outputFormat

Output a single integer — the minimum cost (number of eroded cells) required to transform a theoretical worm B into the fossil worm A.

sample

1
3
5

0

</p>