题目描述

给定两个长度为 $n$ 的序列 $a, b$，找出一个长为 $n$ 的序列 $c$，满足对于 $i = 1, 2, \cdots, n$，有 $c_i = a_i$ 或 $c_i = b_i$，使得 $\sum_{i=2}^{n} |c_i - c_{i-1}|$ 最小，你只需要输出这个最小值。

输入格式

• 输入的第一行包含一个正整数 $n$。
• 接下来一行 $n$ 个整数，表示序列 $a_i$。
• 接下来一行 $n$ 个整数，表示序列 $b_i$。

输出格式

输出一行一个整数，表示 $\sum_{i=2}^{n} |c_i - c_{i-1}|$ 的最小值。

输入输出样例

5
1 3 4 2 5
2 5 4 2 1

5

说明/提示

样例 1 解释

令序列 $c = [2, 3, 4, 2, 1]$，此时 $\sum_{i=2}^{n} |c_i - c_{i-1}| = 5$，可以证明不存在更小的答案。

样例 2

见附件的 seq/seq2.in 与 seq/seq2.ans。

数据范围

• 对于 $20\%$ 的数据，满足 $n\leq 20$。
• 对于 $100\%$ 的数据，满足 $1\leq n\leq 2\times 10^5$，$0\leq |a_i|,|b_i|\leq 10^9$。

1
565215927
-577807166

0

2
48171837 169175028
794471370 -926642783

121003191