Description

母牛Mustang在家里研究跳棋，她的跳棋是由n个格子排成一条线组成的，每个格子上有一个数字。这些格子从左到右编号为1～n。 母牛每走一步都需要消耗一定的青草。从格子i跳到格子j所消耗的青草是两个格子上数字的差的绝对值。 每个格子能够往右跳到一个区间[l,r]内的格子上。不在这个区间内的格子不能跳。

在最开始，母牛在1号位置。现在母牛想知道自己跳到n号点最少需要花费多少青草。

Input

第一行是一个整数 n，表示有n个格子。 接下来一行是n个整数，表示每个格子上的数字a_i。 接下来是n-1行，每行两个数字l, r, 表示第i个格子可以跳到的区间。第n个格子没有可以跳的区间

$(0 < n <= 1000) ( i < l_i <= r_i <= n ) ( 0 < a_i < 1000000000 )$

Output

输出一个整数，表示从$1$到$n$最少花费的青草。

Sample Input

4
1 2 3 4
2 2
3 3
4 4

Sample Output

3