畀你一個由 $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]$ 係最優嘅。