給定一個由 $n$ 個正整數組成的陣列 $a$。然而,陣列 $a$ 中的某些元素缺失了,它們被替換成了零。
定義 $a$ 在區間 $[\ell, r]$ 上的振幅(oscillation)為 $\max(a_\ell, \dots, a_r) - \min(a_\ell, \dots, a_r)$。
給定 $q$ 個形如 $[\ell_i, r_i]$ 的區間。請將 $a$ 中的每個零替換為一個正整數,以最小化 $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]$ 是最優的。