给你一个由 $n$ 个正整数组成的数组 $a$。然而，数组 $a$ 中的某些元素缺失了，它们被替换为了 $0$。

定义 $a$ 在区间 $[\ell, r]$ 上的波动值为 $\max(a_\ell, \dots, a_r) - \min(a_\ell, \dots, a_r)$。

给你 $q$ 个形如 $[\ell_i, r_i]$ 的区间。请将 $a$ 中的每个 $0$ 替换为一个正整数，以最小化 $a$ 在所有 $q$ 个区间上的波动值之和。

输入格式

第一行包含两个整数 $n$ 和 $q$ ($1 \le n, q \le 2 \cdot 10^5$)。

第二行包含 $n$ 个整数 $a_1, \dots, a_n$ ($0 \le a_i \le 10^9$)，表示数组的元素。其中 $a_i = 0$ 表示第 $i$ 个元素缺失。

接下来的 $q$ 行描述这些区间。每行包含两个整数 $\ell_i$ 和 $r_i$ ($1 \le \ell_i \le r_i \le n$)。

输出格式

输出一个整数：在所有给定的区间上，$a$ 的波动值之和的最小值。

样例

输入样例 1

5 2
2 1 0 3 2
1 3
3 5

输出样例 1

2

输入样例 2

5 3
1 0 3 0 1
1 2
2 4
5 5

输出样例 2

2

输入样例 3

7 4
4 4 0 1 0 3 4
1 3
1 3
3 5
4 7

输出样例 3

6

说明

在第一个样例中，唯一的最优数组为 $a = [2, 1, 2, 3, 2]$。

在第二个样例中，存在多个最优数组。例如，$a = [1, 2, 3, 2, 1]$ 是最优的。

在第三个样例中，存在多个最优数组。例如，$a = [4, 4, 4, 1, 2, 3, 4]$ 是最优的。