You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

有一个1*n的棋盘，上面有若干个棋子，一个格子上可能有多个棋子。

你每次操作是先选择一个棋子，然后选择以下两个操作中的一个：

~若该棋子不在 (1,1)，让这个棋子往左走一格，即从 (1,x) 走到 (1,x-1)。

~若该棋子不在 (1,n)，且这个棋子曾经到达过(1,1)，让这个棋子往右走一格，即从 (1,x) 走到 (1,x+1)。

给定一开始每个格子上有几个棋子，再给定目标局面每个格子上需要几个棋子，求最少需要多少次操作。

输入描述

每组测试数据描述如下：

第一行一个正整数 n ( 1 <= n <= 10⁵ ) 表示棋盘大小。

第二行n个非负整数 a_i ( 1 <= $\sum_{i = 1}^{n}\$ a_i <= 10⁹ ) 表示一开始 1 ~ i 上有几个棋子。

第三行n个非负整数 b_i ( 1 <= $\sum_{i = 1}^{n}\$ b_i <= 10⁹ ) 表示目标局面里 1 ~ i 上有几个棋子。

确保$\sum_{i = 1}^{n}\$ a_i 与 $\sum_{i = 1}^{n}\$ b_i 相等

输出描述

输出一个非负整数，表示最少需要几次操作。

样例

5
0 0 1 1 0
1 0 0 0 1

9

解释

对题目中样例的解释：

先把(1,3)上的棋子走到(1,1)，花费了2次操作。

然后把(1,4)上的棋子走到(1,1)，再往右走到(1,5)，花费了 3+4=7次操作。

所以一共花了9次操作。