题目描述

AtCoDeer君看到桌上放着 $N$ 个细长的长方形。把桌面看作平面，则如下图所示：第 $i(1 \leq i \leq N)$ 个长方形占了纵 $[i-1,i]$ ，横 $[l_i,r_i]$ 的空间。

AtCoDeer可以移动每个长方形，来使所有长方形连接起来。每个长方形横向移动 $x$ 的距离其代价为 $x$ 。请求出将所有长方形连接所需的最小代价。可以证明答案一定为整数。

数据范围

• 对于 $30\%$ 的数据：
• $1 \leq N \leq 400$
• $1 \leq l_i < r_i \leq 400$
• 对于 $100\%$ 的数据：
• 输入全为整数。
• $1 \leq N \leq 10^5$
• $1 \leq l_i < r_i \leq 10^9$

输入

输入按以下形式：

输出

输出必要代价的最小值。

样例

样例见原题面； 样例 2,5 的输出都为 $0$ 。

样例解释

样例1解释

将第 $2$ 个长方形向左移动 $2$ 单位长度时代价最小。

样例2解释

开始时长方形间就是连接的，所有没必要进行移动。

感谢@ミク 提供的翻译